Laufzeitabschätzung

[Daniela.S]

Hallo loirad,

Ich denke schon, dass hier einiges fehlt.
Hier mal eine hoffentlich vollständige Auflistung, gewichtet nach Aufwand...


O(1) konstanter Aufwand (optimal)
O(ld N) logarithmischer Aufwand
O(√N) Aufwand mit Wurzel N
O(N) linearer Aufwand
O(N*ld N) quasilinearer Aufwand
O(N²) quadratischer Aufwand
O(Nᵏ) polynomieller Aufwand
O(2ᴺ) exponentieller Aufwand
O(N!) faktorieller Aufwand (am schlechtesten)

Je nachdem, welche Funktion du hast zB. Logarithmus, kannst du die entsprechende O-Notation anwenden. Die O-Notation gibt nur die obere Schranke für den asymptotischen Verlauf des Aufwandes an. Die gesamte Notation kann vereinfacht werden, indem man nur den aufwendigsten Teil hernimmt und kürzt.
zB.
O(20N²+8N+200) => O(N²)

Vielleicht hilft dir das noch weiter...


liebe Grüße,
Daniela

[loirad]

Ok danke! Ich habe die Klausur inzwischen hinter mich gebracht - der Teil zur Laufzeitberechnung war recht klein gehalten. Ich denke das müsste ich hinbekommen haben. Trotzdem Danke für die Mühe!

[Daniela.S]

Naja, ein bisschen früher nachfragen wäre hilfreich gewesen. Drücke dir trotzdem dei Daumen, dass alles gut gelaufen ist