θ-Symbol (Theta)

Betrachten wir eine einfache Implementation der linearen Suche:

Lass uns die Größe des Arrays (array.length) mit $n$n bezeichnen. Dann ist die maximale Anzahl Durchläufe der for-Schleife $n$n. Dieser schlechteste Fall tritt dann ein, wenn der gesuchte Wert im Array gar nicht vorkommt.

Bei jeder Ausführung der Schleife, müssen mehrere Dinge gemacht werden:

Jede dieser kleinen Berechnungen benötigt bei jeder Ausführung eine konstante Zeitspanne. Wenn die for-Schleife $n$n mal iteriert, dann ist die Zeit für alle $n$n Iterationen $c_1 \cdot n$c, start subscript, 1, end subscript, dot, n, wobei $c_1$c, start subscript, 1, end subscript die Summe der Zeiten für die Berechnungen in einer Schleifeniteration ist. Leider kennen wir hier aber den Wert von $c_1$c, start subscript, 1, end subscript nicht, da dieser von der Geschwindigkeit des Prozessors, der verwendeten Programmiersprache, Compilers oder Interpreters, der den Quellcode in ausführbaren Maschinencode umwandelt, und anderen Faktoren abhängt.

Dieser Code hat ein wenig zusätzlichen Overhead, um die for-Schleife einzurichten (einschließlich der Initialisierung von guess auf 0) und möglicherweise der Rückgabe von -1 am Ende. Nennen wir die Zeit für diesen Overhead $c_2$c, start subscript, 2, end subscript, was auch eine Konstante ist. Daher ist die Gesamtzeit für die lineare Suche im schlimmsten Fall $c_1 \cdot n + c_2$c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.

Wie wir bereits gesehen haben, sagen der konstante Faktor $c_1$c, start subscript, 1, end subscript und der niederwertige Term $c_2$c, start subscript, 2, end subscript nichts über die Wachstumsrate der Laufzeit aus. Bedeutsam ist hingegen, dass die Worst-case Laufzeit der linearen Suche mit der Arraygröße $n$n wächst. Die Notation, die wir für diese Laufzeit verwenden, ist $\Theta (n)$\Theta, left parenthesis, n, right parenthesis. Das ist der griechische Buchstabe "Theta", und wir sagen "big-Theta von $n$n" oder einfach nur "Theta von $n$n".

Wenn eine bestimmte Laufzeit $\Theta (n)$\Theta, left parenthesis, n, right parenthesis ist, dann bedeutet dies, dass wenn $n$n groß genug wird, die Laufzeit mindestens $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n und höchstens $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n für die Konstanten $k_1$k, start subscript, 1, end subscript und $k_2$k, start subscript, 2, end subscript ist. Man kann sich $\Theta (n)$\Theta, left parenthesis, n, right parenthesis so vorstellen:

Für kleine Werte von $n$n ist uns gleichgültig, wie die Laufzeit im Vergleich zu $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n oder $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n ist. Aber sobald $n$n groß genug ist - also auf oder rechts von der gestrichelten Linie - muss die Laufzeit zwischen $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n und $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n liegen. Solange die Konstanten $k_1$k, start subscript, 1, end subscript und $k_2$k, start subscript, 2, end subscript existieren, sagen wir, dass die Laufzeit $\Theta (n)$\Theta, left parenthesis, n, right parenthesis ist.

Wir sind übrigens nicht auf $n$n in Big-Θ Notation beschränkt. Wir können jede Funktion verwenden, wie z. B. $n ^ 2$n, squared, $n \log_2 n$n, log, start base, 2, end base, n oder jede andere Funktion von $n$n. Man kann siech eine Laufzeit von $\Theta (f (n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis für eine beliebige Funktion $f (n)$f, left parenthesis, n, right parenthesis so vorstellen:

Sobald $n$n groß genug ist, liegt die Laufzeit zwischen $k_1 \cdot f (n)$k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis und $k_2 \cdot f (n)$k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.

Ein weiterer Vorteil der Verwendung der Big-Θ-Notation ist, dass wir uns keine Sorgen machen müssen, welche Zeiteinheiten wir verwenden. Angenommen, wir berechnen, dass eine Laufzeit $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 Mikrosekunden ist. Oder vielleicht sind es auch Millisekunden? Wenn du die Big-Θ Notation benutzt, nennst Du keine Zeiteinheit. In der Praxis suchen wir den bestimmenden Term und lassen also Konstanten und Terme geringerer Ordnung fallen. Du lässt also den Faktor 6 und die Terme $100n + 300$100, n, plus, 300 fallen, und gibst lediglich an, dass die Laufzeit $\Theta (n ^ 2)$\Theta, left parenthesis, n, squared, right parenthesis ist.

Wenn wir die Big-Θ Notation verwenden, sagen wir, dass wir ein asymptotisch enges Intervall der Laufzeit haben. "Asymptotisch", weil es nur für große Werte von $n$n zutrifft ist. "Intervall", weil die Laufzeit nach oben und nach unten beschränkt ist.

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.