Hauptinhalt

Kurs: Informationstechnik > Lerneinheit 1

Lektion 3: Asymptotische Notation

θ-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

c_{1} \cdot n

, wobei

c_{1}

die Summe der Zeiten für die Berechnungen in einer Schleifeniteration ist. Leider kennen wir hier aber den Wert von

c_{1}

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}

, was auch eine Konstante ist. Daher ist die Gesamtzeit für die lineare Suche im schlimmsten Fall

c_{1} \cdot n + c_{2}

Wie wir bereits gesehen haben, sagen der konstante Faktor

c_{1}

und der niederwertige Term

c_{2}

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

k_{1} \cdot n

und höchstens

k_{2} \cdot n

für die Konstanten

k_{1}

und

k_{2}

ist. Man kann sich

Θ (n)

so vorstellen:

Für kleine Werte von

n

ist uns gleichgültig, wie die Laufzeit im Vergleich zu

k_{1} \cdot n

oder

k_{2} \cdot n

ist. Aber sobald

n

groß genug ist - also auf oder rechts von der gestrichelten Linie - muss die Laufzeit zwischen

k_{1} \cdot n

und

k_{2} \cdot n

liegen. Solange die Konstanten

k_{1}

und

k_{2}

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.

n^{2}

n \log_{2} n

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

k_{1} \cdot f (n)

und

k_{2} \cdot f (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

6 n^{2} + 100 n + 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

100 n + 300

fallen, und gibst lediglich an, dass die Laufzeit

Θ (n^{2})

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?

Anmelden

Sortiere nach:

Noch keine Beiträge.

Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.