Funktionen in asymptotischer Schreibweise

Wenn wir die asymptotische Notation verwenden, um die Wachstumsrate der Laufzeit eines Algorithmus in Bezug auf die Eingabegröße $n$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$n angeben, könnte man die Laufzeit dieses Algorithmus als $\Theta (n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis angeben. Warum? Weil $n^0 = 1$n, start superscript, 0, end superscript, equals, 1 ist und die Laufzeit des Algorithmus ein konstantes Vielfaches von 1 ist. In der Praxis schreiben wir allerdings nicht $\Theta (n ^ 0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis sondern $\Theta (1)$\Theta, left parenthesis, 1, right parenthesis.

Angenommen, ein Algorithmus dauert $\Theta (\log_ {10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis. Ebensogut könnte man die Laufzeit als $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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$a, $b$b, and $n$n. Wenn $a$a and $b$b konstant sind, dann unterscheiden sich $\log_a n$log, start base, a, end base, n und $\log_b n$log, start base, b, end base, n nur durch den Faktor $\log_b a$log, start base, b, end base, 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 $\Theta (\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis für jeden positiv konstanten Wert von $a$a ist. Warum? Die Anzahl der Vermutungen ist höchstens $\log_2 n + 1$log, start base, 2, end base, n, plus, 1. Das Erzeugen und Testen jedes Ratewertes nimmt eine konstante Zeit in Anspruch, ebenso die Einrichtung und Rückgabe. Die Binärsuche dauert also $\Theta (\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, 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$a und $b$b Konstanten sind und $a <b$a, is less than, b ist, dann wächst eine Laufzeit von $\Theta (n ^ a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis langsamer als eine Laufzeit von $\Theta (n ^ b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis . Zum Beispiel wächst eine Laufzeit von $\Theta (n)$\Theta, left parenthesis, n, right parenthesis, die ja $\Theta (n ^ 1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis ist, langsamer als eine Laufzeit von $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis. Die Exponenten müssen dabei keine ganzen Zahlen sein. Zum Beispiel wächst eine Laufzeit von $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis langsamer als eine Laufzeit von $\Theta (n ^ 2 \sqrt {n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, was $\Theta (n ^ {2{,}5})$\Theta, left parenthesis, n, start superscript, 2, comma, 5, end superscript, right parenthesis ist.

Das folgende Diagramm vergleicht das Wachstum von $n$n,$n^2$n, squared und $n^{2.5}$n, start superscript, 2, point, 5, end superscript:

Logarithmen wachsen langsamer als Polynome. Das heißt, dass $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis langsamer wächst als $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis für beliebige positive Werte für $a$a. Aber da der Wert von $\log_2 n$log, start base, 2, end base, n mit steigendem $n$n wächst, wächst $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis schneller als $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Das folgende Diagramm vergleicht das Wachstum von $1$1, $n$n und $\log_2 n$log, start base, 2, end base, 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$a, start superscript, n, end superscript, mit $a > 1$a, is greater than, 1, schneller wächst as eine polynomische Funktion $n^b$n, start superscript, b, end superscript, mit $b$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.