Funktionen in asymptotischer Schreibweise

Wenn wir die asymptotische Notation verwenden, um die Wachstumsrate der Laufzeit eines Algorithmus in Bezug auf die Eingabegröße $n$‍ zum Ausdruck zu bringen, ist es gut, ein paar Dinge im Hinterkopf zu behalten.

Fangen wir mit etwas einfachem an. Angenommen, ein Algorithmus benötigt eine konstante Ausführungszeit, unabhängig von der Eingabegröße. Als Beispiel betrachten wir ein Array, das bereits in aufsteigender Reihenfolge sortiert ist. Du willst darin das minimale Element finden. Das würde dann unabhängig von der Größe des Arrays immer eine konstante Zeit dauern, da das minimale Element stets bei Index 0 anzufinden ist. Da wir die asymptotische Notation gerne als Funktion in Abhängigkeit von $n$‍ angeben, könnte man die Laufzeit dieses Algorithmus als $\mathrm{\Theta }(n^0)$‍ angeben. Warum? Weil $n^0=1$‍ ist und die Laufzeit des Algorithmus ein konstantes Vielfaches von 1 ist. In der Praxis schreiben wir allerdings nicht $\mathrm{\Theta }(n^0)$‍ sondern $\mathrm{\Theta }(1)$‍.

Angenommen, ein Algorithmus dauert $\mathrm{\Theta }({\log }_{10}n)$‍. Ebensogut könnte man die Laufzeit als $\mathrm{\Theta }({\log }_{2}n)$‍ angeben. Wenn die Basis des Logarithmus eine Konstante (2,10, usw.) ist, spielt es keine Rolle, welche Basis wir in der asymptotischen Notation verwenden. Was ist der Grund dafür? Es gibt eine mathematische Formel, die besagt:

für alle positiven Zahlen $a$‍, $b$‍, and $n$‍. Wenn $a$‍ and $b$‍ konstant sind, dann unterscheiden sich ${\log }_{a}n$‍ und ${\log }_{b}n$‍ nur durch den Faktor ${\log }_{b}a$‍, und das ist ein konstanter Faktor, denn wir bei der asymptotischen Notation vernachlässigen dürfen.

Daher können wir sagen, dass die Worst-Case-Laufzeit der Binärsuche $\mathrm{\Theta }({\log }_{a}n)$‍ für jeden positiv konstanten Wert von $a$‍ ist. Warum? Die Anzahl der Vermutungen ist höchstens ${\log }_{2}n+1$‍. Das Erzeugen und Testen jedes Ratewertes nimmt eine konstante Zeit in Anspruch, ebenso die Einrichtung und Rückgabe. Die Binärsuche dauert also $\mathrm{\Theta }({\log }_{2}n)$‍, Wir verwenden dabei den Logarithmus zur Basis 2 weil Informatiker gerne in Potenzen von 2 denken.

Wenn wir mit asymptotischer Notation arbeiten sehen wir eine Ordnung der häufig verwendeten Funktionen. Wenn $a$‍ und $b$‍ Konstanten sind und $a<b$‍ ist, dann wächst eine Laufzeit von $\mathrm{\Theta }(n^a)$‍ langsamer als eine Laufzeit von $\mathrm{\Theta }(n^b)$‍ . Zum Beispiel wächst eine Laufzeit von $\mathrm{\Theta }(n)$‍, die ja $\mathrm{\Theta }(n^1)$‍ ist, langsamer als eine Laufzeit von $\mathrm{\Theta }(n^2)$‍. Die Exponenten müssen dabei keine ganzen Zahlen sein. Zum Beispiel wächst eine Laufzeit von $\mathrm{\Theta }(n^2)$‍ langsamer als eine Laufzeit von $\mathrm{\Theta }(n^2\sqrt{n})$‍, was $\mathrm{\Theta }(n^{2,5})$‍ ist.

Das folgende Diagramm vergleicht das Wachstum von $n$‍,$n^2$‍ und $n^{2.5}$‍:

Logarithmen wachsen langsamer als Polynome. Das heißt, dass $\mathrm{\Theta }({\log }_{2}n)$‍ langsamer wächst als $\mathrm{\Theta }(n^a)$‍ für beliebige positive Werte für $a$‍. Aber da der Wert von ${\log }_{2}n$‍ mit steigendem $n$‍ wächst, wächst $\mathrm{\Theta }({\log }_{2}n)$‍ schneller als $\mathrm{\Theta }(1)$‍.

Das folgende Diagramm vergleicht das Wachstum von $1$‍, $n$‍ und ${\log }_{2}n$‍:

Hier ist eine Liste von Funktionen in asymptotische Notation, denen wir bei der Analyse von Algorithmen oft begegnen. Wir sortieren sie nach ihrer Wachstumsgeschwindigkeit - von langsam nach schnell:

Beachte, dass die Exponentialfunktion $a^n$‍, mit $a>1$‍, schneller wächst as eine polynomische Funktion $n^b$‍, mit $b$‍ als Konstante.

Diese Liste ist nicht erschöpfend; es gibt viele Algorithmen, deren Laufzeiten hier nicht angezeigt werden. Du wirst hoffentlich ein paar davon auf deiner Reise durch die Informatik treffen.

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.