If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

O-Symbol

Wir verwenden die Big-Θ Notation, um asymptotisch das Wachstum der Laufzeit einer Funktion nach oben und unten zu begrenzen. Manchmal wollen wir aber nur die obere Schranke betrachten.
Zum Beispiel, obwohl die Worst-Case-Laufzeit der binären Suche Θ(log2n) ist, wäre es falsch zu sagen, dass die binäre Suche in jedem Fall Θ(log2n) Zeit in Anspruch nimmt. Was passiert, wenn wir den Zielwert bei der ersten Vermutung finden? Dann läuft der Algorithmus in Θ(1) Zeit. Die Laufzeit der binären Suche ist niemals schlechter als Θ(log2n), aber sie ist manchmal besser.
Es wäre praktisch, eine Form von asymptotischer Notation zu haben, die angibt, dass "die Laufzeit höchstens so stark wächst, aber sie könnte auch langsamer wachsen." Wir verwenden die "Big-O" Notation für solche Zwecke.
Wenn eine Laufzeit O((n)) ist, dann ist für große n die Laufzeit höchstens kf(n) für die Konstante k. Man kann sich eine O(f(n)) Laufzeit so vorstellen:
6n^2 vs 100n+300
Wir sagen, dass die Laufzeit "Big-O von f(n)", oder nur "O von f(n)" ist. Wir verwenden die Big-O-Notation für asymptotische Obergrenzen , da sie das Wachstum der Laufzeit nach oben für hinreichend große Eingangsgrößen begrenzt.
Wir können nun die Laufzeit der Binärsuche in allen Fällen charakterisieren. Die Laufzeit der Binärsuche ist immer O(log2n) ist. Wir können eine genauere Aussage über die Worst-Case-Laufzeit treffen: Sie ist Θ(log2n). Aber die beste Aussage, die alle Fälle abdeckt ist, dass die binäre Suche in O(log2n) Zeit läuft.
Wenn wir uns nochmal die Definition der Big-Θ Notation anschauen, stellen wir fest, dass sie der Big-O Notation stark ähnelt, mit dem Unterschied dass die Big-Θ Notation die Laufzeit von oben und unten, anstatt nur von oben, begrenzt. Wenn wir sagen, dass eine Laufzeit in einer bestimmten Situation Θ(f(n)) ist, dann ist sie auch O(f(n)). Zum Beispiel können wir sagen, dass, weil die Worst-Case-Laufzeit der binären Suche Θ(log2n) ist, sie deswegen auch O(log2n) ist.
Der Umkehrschluß ist jedoch nicht unbedingt wahr: Wie wir gesehen haben, läuft die binäre Suche immer in O(log2n) Zeit, aber nicht immer in Θ(log2n).
Da die Big-O Notation nur eine asymptotische obere Schranke und keine asymptotisch enge Schranke angibt, können wir Aussagen machen, die auf den ersten Blick falsch erscheinen, aber technisch korrekt sind. Zum Beispiel ist es absolut korrekt zu sagen, dass die binäre Suche in O(n) Zeit läuft. Das liegt daran, dass die Laufzeit nicht schneller wächst als eine Konstante mal n. Tatsächlich wächst sie langsamer.
Stell dir das so vor. Angenommen, du hast 10 Euro in deiner Tasche. Du gehst zu deinem Freund und sagst: "Ich habe einen Geldbetrag in meiner Tasche und ich garantiere, dass es nicht mehr als eine Million Euro ist." Deine Aussage ist absolut wahr, wenn auch nicht furchtbar präzise.
Eine Euro Dollar ist eine obere Schranke für 10 Dollar, so wie O(n) eine obere Schranke für die Laufzeit der binären Suche ist. Andere, ungenaue, obere Schranken für die binäre Suche wären O(n2), O(n3) und O(2n). Aber keine von Θ(n), Θ(n2), Θ(n3) und Θ(2n) wäre in jedem Fall richtig, um die Laufzeit der binären Suche zu beschreiben.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.