Auf Folie I-28 geht es um die Implementierung von Mengen als Bitvektorn. Dazu ist die Komplexität von diversen Operationen angeben, u.a. ist für insert eine Komplexität von O(1) angeben. Sollte das nicht eigentlich O(n) sein, da jedes neue Element gegen alle vorhandenen Elemente auf Duplizität geprüft werden muss?

Gibt es irgendwo eine verständlichere Definition der Komplexität und deren Berechnung?

Auf Folie I-53 geht es um den Aufbau von binären Suchbäumen. Angegeben sind vier Beispiele, die je um das Element 4 erweietrt werden soll. Ist das so richtig:

| 1 5 7 1 5 7 4 | (1) (1) | \ \ | (5) (5) | \ / \ | (7) (4) (7)
| 7 5 1 7 5 1 4 | (7) (7) | / / | (5) (5) | / / | (1) (1) | \ | (4)
| 7 1 5 7 1 5 4 | (7) (7) | / / | (1) (1) | \ \ | (5) (5) | / | (4)

| 5 1 7 5 1 7 5 | (5) (5) | / \ / \ | (1) (7) (1) (7) | \ | (4)

[…] Mengen als Bitvektorn. […] für insert eine Komplexität von O(1) […]
Sollte das nicht eigentlich O(n) sein, da jedes neue Element gegen alle vorhandenen Elemente auf Duplizität geprüft werden muss?

Noe, Du siehst ja sofort anhand des Index, ob das Bit belegt ist oder nicht. Nehmen wir mal an, Du willst von 32 Personen die Information speichern, ob sie schon bezahlt haben oder nicht (was auch immer). Dafür kann man ja zB eine 32 Bit breite Variable nehmen, die setzt man dann zunächst erst mal auf 0.

Wenn man jetzt wissen will, ob Person n schon bezahlt hat, dann schaut man sich einfach das Bit mit der Nummer n an. Setzen können wir das entsprechende Bit mit bitweise-oder.

unsigned int menge = 0; unsigned int bezahlt(int n) { return menge & (1 << n); } void bezahlen(int n) { menge |= (1 << n); }
Das soll C sein, getestet habe ich es nicht. Und jetzt bitte keine Diskussion um die Breite von int auf 286 Rechnern [img]http://www.fb18.de/gfx/24.gif[/img]