kleine formalität zwischendurch:
wenn einer die definition der mengen zugrundelegt, dann bezeichnet N eine funktion g mit g(N) = N; entsprechend N^2: h(N) = N^2.

die landau notation soll aber auch hilfreich beim rechnen sein, jedenfalls hat das mal der stochastik dozent gemeint in einer vorlesung, in die ich mal rein bin =)
dadurch kann man sich nämlich viel firlefanz mit zu vernachlässigenden termen sparen; afaik angewandt z.b. bei der stirlingschen formel, wo am ende einfach gesagt wird, dass man noch was addieren muss, was mit O(1/N) wächst. (gr, finde irgendwie keinen schönen link)

Ganz genau:

Wen ein Algorithmus die Komplexität O(f(n)) hat, dann gibt es eine Konstante c, so dass für alle n gilt: Die Laufzeit ist kleinergleich c * f(n) (* konstanter Zeitverbrauch). Wichtig ist, dass es ein und dieselbe  Konstante c für alle n ist.


Manchmal kann für kleine n ein Algorithmus mit quadratischer Komplexität (also O(n^2)) trotzdem schneller sein als einer mit O(n log n)

Ich habe gesehen, dass es mehrere Landausche Symbole gibt.
O steht dabei für the worst case. Für was sind die anderen? Und kann ich die genauso einsetzen wie O? Für was gibt es die? Einfach nur zum Abschätzen der Laufzeit?

ja, z.B. für die Laufzeit... und O ist nicht immer worst-case :)

laufzeit ist eine metrik. eine andere ist z.b. bitlaenge.

[quote=esskar,02.08.2004, 17:54]ja, z.B. für die Laufzeit... und O ist nicht immer worst-case :)[/quote]
Was kann es auch sein?

O bezeichnet /nur/ eine sog. /enge/ obere schranke.
es kann best-, average-, und worst case verhalten gemeint sein.
das muss mit dabeistehen. ansonsten kannst du mit einem dreiseitigen wuerfel wuerfeln

;)

@eb: hast du dir meine Links eigentlich mal angeschaut?

Es gibt noch Symbole für untere Schranken und für beides zusammen.

[quote=esskar,03.08.2004, 02:37]@eb: hast du dir meine Links eigentlich mal angeschaut?[/quote]
Ja, allerdings ist das ganze nicht so einfach.
Mit dem bisherigen habe ich aber ja schon eine gute Basis. :)