If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

θ-Symbol (Theta)

Betrachten wir eine einfache Implementation der linearen Suche:
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // found it!
    }
  }
  return -1;  // didn't find it
};
Lass uns die Größe des Arrays (array.length) mit n bezeichnen. Dann ist die maximale Anzahl Durchläufe der for-Schleife 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:
  • vergleiche guess mit array.length
  • vergleiche array[guess] mit targetValue
  • liefere eventuell den Wert von guess
  • erhöhe guess.
Jede dieser kleinen Berechnungen benötigt bei jeder Ausführung eine konstante Zeitspanne. Wenn die for-Schleife n mal iteriert, dann ist die Zeit für alle n Iterationen c1n, wobei c1 die Summe der Zeiten für die Berechnungen in einer Schleifeniteration ist. Leider kennen wir hier aber den Wert von c1 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 c2, was auch eine Konstante ist. Daher ist die Gesamtzeit für die lineare Suche im schlimmsten Fall c1n+c2.
Wie wir bereits gesehen haben, sagen der konstante Faktor c1 und der niederwertige Term c2 nichts über die Wachstumsrate der Laufzeit aus. Bedeutsam ist hingegen, dass die Worst-case Laufzeit der linearen Suche mit der Arraygröße n wächst. Die Notation, die wir für diese Laufzeit verwenden, ist Θ(n). Das ist der griechische Buchstabe "Theta", und wir sagen "big-Theta von n" oder einfach nur "Theta von n".
Wenn eine bestimmte Laufzeit Θ(n) ist, dann bedeutet dies, dass wenn n groß genug wird, die Laufzeit mindestens k1n und höchstens k2n für die Konstanten k1 und k2 ist. Man kann sich Θ(n) so vorstellen:
Für kleine Werte von n ist uns gleichgültig, wie die Laufzeit im Vergleich zu k1n oder k2n ist. Aber sobald n groß genug ist - also auf oder rechts von der gestrichelten Linie - muss die Laufzeit zwischen k1n und k2n liegen. Solange die Konstanten k1 und k2 existieren, sagen wir, dass die Laufzeit Θ(n) ist.
Wir sind übrigens nicht auf n in Big-Θ Notation beschränkt. Wir können jede Funktion verwenden, wie z. B. n2, nlog2n oder jede andere Funktion von n. Man kann siech eine Laufzeit von Θ(f(n)) für eine beliebige Funktion f(n) so vorstellen:
Sobald n groß genug ist, liegt die Laufzeit zwischen k1f(n) und k2f(n).
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 6n2+100n+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 fallen, und gibst lediglich an, dass die Laufzeit Θ(n2) 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 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.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.