Asymptotische Notation

Bisher haben wir "linear search" (lineare Suche) und binary search (binäre Suche) analysiert, indem wir die maximale Anzahl der Versuche die wir brauchen gezählt haben. Was wir aber wirklich wissen wollen ist wie lange diese Algorithmen brauchen. Wir interessieren uns für die Dauer, nicht nur für die Anzahl der Versuche. Die Laufzeit von linear search und binary search beinhaltete die Zeit, die notwendig ist, um diese Versuche zu machen, aber sie umfasst noch mehr.

Die Laufzeit eines Algorithmus hängt davon ab, wie lange der Computer braucht, um die Befehlszeilen abzuarbeiten. Neben anderen Faktoren hängt dies von der Geschwindigkeit des Computers, von der Programmiersprache und vom Compiler, der für den Computer das Programm von Programmiersprache in den Code übersetzt den der Computer versteht, ab.

Schauen wir uns die Laufzeit eines Algorithmus im Detail an. Wie haben hier eine Kombination von zwei Faktoren. Zuerst müssen wir wissen wie lange der Algorithmus braucht (abhängig von der Datenmenge). Klar, je größer, desto länger, richtig? Wir haben schon gesehen, dass die maximale Anzahl der Versuche in linear search und binary search steigt, wenn die Länge des Eingabefeldes zunimmt. Denk zum Beispiel an ein GPS. Wenn es nur das Autobahnnetz kennen würde und nicht jede kleine Straße, dann sollte es die Route schneller finden, richtig? Daher ist die Laufzeit eines Algorithmus eine Funktion der Größe der Eingabedaten.

Der zweite Faktor ist das Wachstum der Funktion mit der Größe der Eingabedaten. Wir nennen das die Wachstumsrate der Laufzeit. Um die Dinge überschaubar zu halten, müssen wir die Funktion so vereinfachen, dass wir auf den wichtigen Teil fokussieren und die weniger wichtigen Faktoren vernachlässigen. Nehmen wir zum Beispiel an, dass ein Algorithmus, der eine Eingabedatenmenge von $n$‍ hat, $6n^2+100n+300$‍ Maschinenbefehle braucht. Der Ausdruck $6n^2$‍ wird in diesem Fall größer, als der restliche Ausdruck $100n+300$‍ sobald $n$‍ groß genug ist. Hier ist ein Diagramm, das die Werte $6n^2$‍ und $100n+300$‍ für $n$‍ von 0 bis 100 zeigt:

Wir stellen fest, dass die Laufzeit des Algorithmus mit $n^2$‍ wächst, wenn wir den Koeffizienten 6 weglassen wie auch den restlichen Ausdruck $100n+300$‍. Es macht keinen Unterschied welchen Koeffizienten wir verwenden. Solange die Laufzeit $a{n}^2+bn+c$‍ ist, gibt es für die Faktoren $a>0$‍, $b$‍ und $c$‍ immer einen Wert von $n$‍ für den $a{n}^2$‍ größer ist als $bn+c$‍. Und dieser Unterschied wächst, mit größerem $n$‍. Hier siehst du ein Diagramm, dass die Werte für$0,6n^2$‍ und $1000n+3000$‍ zeigt. Wir haben also den Koeffizienten von $n^2$‍ durch 10 dividiert und die anderen zwei Faktoren mit 10 multipliziert.

Der Wert von $n$‍ bei dem $0,6n^2$‍ größer als $1000n+3000$‍ wird, ist größer geworden, aber es wird immer einen Schnittpunkt der Kurven geben, egal welche Faktoren wir verwenden.

Wenn wir die weniger wichtigen Ausdrücke vernachlässigen und die Koeffizienten weglassen, können wir uns auf den wichtigen Teil der Laufzeit des Algorithmus konzentrieren—seine Wachstumsrate— ohne uns in Details zu verlieren. Wenn wir die Koeffizienten und den weniger wichtigen restlichen Ausdruck weglassen, verwenden wir die asymptotische Notation auch Landau Notation genannt. Sie wird durch 3 Symbole charakterisiert: Groß-$\mathrm{\Theta }$‍ Notation, Groß-O Notation und Groß-$\mathrm{\Omega }$‍ Notation.

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.