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 $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis ist, wäre es falsch zu sagen, dass die binäre Suche in jedem Fall $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis Zeit in Anspruch nimmt. Was passiert, wenn wir den Zielwert bei der ersten Vermutung finden? Dann läuft der Algorithmus in $\Theta (1)$\Theta, left parenthesis, 1, right parenthesis Zeit. Die Laufzeit der binären Suche ist niemals schlechter als $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, 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))$O, left parenthesis, left parenthesis, n, right parenthesis, right parenthesis ist, dann ist für große $n$n die Laufzeit höchstens $k \cdot f (n)$k, dot, f, left parenthesis, n, right parenthesis für die Konstante $k$k. Man kann sich eine $O(f (n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis Laufzeit so vorstellen:

Wir sagen, dass die Laufzeit "Big-O von $f(n)$f, left parenthesis, n, right parenthesis", oder nur "O von $f(n)$f, left parenthesis, n, right parenthesis" 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(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis ist. Wir können eine genauere Aussage über die Worst-Case-Laufzeit treffen: Sie ist $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. Aber die beste Aussage, die alle Fälle abdeckt ist, dass die binäre Suche in $O (\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis 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 $\Theta (f (n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis ist, dann ist sie auch $O(f (n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Zum Beispiel können wir sagen, dass, weil die Worst-Case-Laufzeit der binären Suche $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis ist, sie deswegen auch $O (\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis ist.

Der Umkehrschluß ist jedoch nicht unbedingt wahr: Wie wir gesehen haben, läuft die binäre Suche immer in $O (\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis Zeit, aber nicht immer in $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis.

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)$O, left parenthesis, n, right parenthesis Zeit läuft. Das liegt daran, dass die Laufzeit nicht schneller wächst als eine Konstante mal $n$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)$O, left parenthesis, n, right parenthesis 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(n^2)$O, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis und $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. Aber keine von $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis und $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis 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.