Laufzeitabschätzung

[loirad]

Hallo liebe Community,

ich schreibe morgen eine Klausur in Informatik über Graphen, Suchbäume und Laufzeitabschätzung. Die ersten beiden Themen gehen so halbwegs. Jedoch habe ich mit der Laufzeitabschätzung so meine Probleme, da das von unserem Lehrer (seine Erklärungsversuche sind nicht allzu erfolgreich...) nicht allzu gut erklärt wurde. Kann mir das bitte jemand kurz und bündig nochmal erklären?

Liebe Grüße
loirad

PS.: Ich bin jetzt soweit, dass ich weiß, bei einer for-Schleife von 0-n ist die Laufzeit O(n). Und wenn 2 ineinander geschachtelt sind, dann O(n²). Und nacheinander 2n. Und wenn die Zählvariable immer halbiert (oder verdoppelt) wird dann log(n). Fehlt da noch etwas?

[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