Laufzeitanalyse

Einführung

Asymptotische Annäherung einer Funktion

Quadratisches Wachstum

Die Laufzeitanalyse untersucht, wie viele Rechenschritte ein Algorithmus benötigt, um ein Problem zu lösen.

Da die tatsächliche Laufzeit eines Programms stark vom Computer abhängt (z. B. Prozessor oder Arbeitsspeicher), betrachtet man nicht die Zeit in Sekunden, sondern die Anzahl der benötigten Operationen.

Diese Anzahl hängt von der Größe der Eingabe ab. Die Eingabegröße wird meist mit [math]\displaystyle{ n }[/math] bezeichnet.

Beispiel:

• Beim Sortieren ist [math]\displaystyle{ n }[/math] die Anzahl der zu sortierenden Werte.
• Beim Durchsuchen einer Liste ist [math]\displaystyle{ n }[/math] die Länge der Liste.

Für kleine Eingaben spielt die Laufzeitanalyse oft kaum eine Rolle, weil selbst langsame Verfahren schnell genug sind. Wichtig wird sie bei großen Datenmengen.

Die Frage lautet dann:

Wie wächst der Aufwand, wenn die Eingabe immer größer wird?

Genau das beschreibt die asymptotische Laufzeit.

Wenn sich die Laufzeit eines Algorithmus durch eine Funktion beschreiben lässt, z. B.

[math]\displaystyle{ f(x)=\frac{1}{x}+x }[/math]

dann erkennt man für große [math]\displaystyle{ x }[/math], dass der Anteil [math]\displaystyle{ \frac{1}{x} }[/math] immer kleiner wird. Das Verhalten der Funktion wird dann fast nur noch durch [math]\displaystyle{ x }[/math] bestimmt.

Deshalb betrachtet man bei der Laufzeitanalyse nur das Verhalten für große Werte von [math]\displaystyle{ n }[/math]. Dieses Verhalten beschreibt man mit der Landau-Notation (Groß-O-Notation), z. B.:

[math]\displaystyle{ \mathcal{O}(n) }[/math], [math]\displaystyle{ \mathcal{O}(n^2) }[/math], [math]\displaystyle{ \mathcal{O}(n \log n) }[/math]

Damit kann man Algorithmen vergleichen, ohne von einer bestimmten Hardware abhängig zu sein.

Wichtige Abgrenzung

Die asymptotische Laufzeitanalyse gibt nicht an, wie viele Sekunden ein Programm wirklich benötigt.

Sie beschreibt nur, wie stark der Aufwand wächst, wenn die Eingabemenge größer wird. Das macht verschiedene Algorithmen vergleichbar.

Szenarien der Laufzeitabschätzung

Bei der Laufzeitanalyse betrachtet man meist drei Fälle:

• Best Case (bester Fall):

 Der Algorithmus arbeitet unter idealen Bedingungen und benötigt minimalen Aufwand.

• Worst Case (schlechtester Fall):

 Der Algorithmus trifft auf die ungünstigste Eingabe und benötigt maximalen Aufwand.

• Average Case (durchschnittlicher Fall):

 Man betrachtet den durchschnittlichen Aufwand bei zufälligen Eingaben.

Diese drei Fälle helfen dabei, das Verhalten eines Algorithmus besser einzuschätzen.

Average-Case und Erwartungswert

Der Average-Case beschreibt die durchschnittliche Laufzeit.

Mathematisch wird diese mit dem Erwartungswert berechnet:

[math]\displaystyle{ E(T)=\sum_{i=1}^{|E|} p_i \cdot t_i }[/math]

Dabei gilt:

• [math]\displaystyle{ t_i }[/math]: Laufzeit bei einer bestimmten Eingabe
• [math]\displaystyle{ p_i }[/math]: Wahrscheinlichkeit dieser Eingabe

Der Erwartungswert ist also:

Laufzeit × Wahrscheinlichkeit

für alle möglichen Eingaben zusammengezählt.

Oft nimmt man an, dass alle Eingaben gleich wahrscheinlich sind. Dann spricht man von einer Gleichverteilung.

---

Beispiel: Lineare Suche

Bei der linearen Suche wird eine Liste von vorne nach hinten durchsucht.

Steht das gesuchte Element:

• an Position 1 → 1 Vergleich
• an Position 2 → 2 Vergleiche
• ...
• an Position [math]\displaystyle{ n }[/math] → [math]\displaystyle{ n }[/math] Vergleiche

Wenn jede Position gleich wahrscheinlich ist, ergibt sich:

[math]\displaystyle{ E(T)=\frac{1}{n}\sum_{i=1}^{n} i }[/math]

Mit der Gaußschen Summenformel:

[math]\displaystyle{ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} }[/math]

folgt:

[math]\displaystyle{ E(T)=\frac{1}{n}\cdot\frac{n(n+1)}{2}=\frac{n+1}{2} }[/math]

Im Durchschnitt benötigt die lineare Suche also etwa halb so viele Vergleiche wie im schlechtesten Fall.

Für große [math]\displaystyle{ n }[/math] dominiert der Term [math]\displaystyle{ n }[/math], daher gilt:

[math]\displaystyle{ \mathcal{O}(n) }[/math]

Beispiel: Laufzeitanalyse von Insertion Sort

Beim Insertion Sort wird jedes neue Element an der richtigen Stelle in den bereits sortierten Teil eingefügt.

Best Case

Der beste Fall liegt vor, wenn die Liste bereits sortiert ist:

[1,2,3,4,5]

Dann genügt pro Element ein Vergleich.

Bei [math]\displaystyle{ n }[/math] Elementen:

[math]\displaystyle{ T(n)=n-1 }[/math]

Das Wachstum ist linear:

[math]\displaystyle{ \mathcal{O}(n) }[/math]

Worst Case

Der schlechteste Fall liegt vor, wenn die Liste rückwärts sortiert ist:

[5,4,3,2,1]

Dann muss jedes neue Element an den Anfang verschoben werden.

Die Anzahl der Vergleiche ist:

[math]\displaystyle{ 1+2+3+\dots+(n-1) }[/math]

Mit Gauß:

[math]\displaystyle{ \frac{n(n-1)}{2} }[/math]

Das ergibt quadratisches Wachstum:

[math]\displaystyle{ \mathcal{O}(n^2) }[/math]

Average Case

Bei zufälliger Reihenfolge liegt das neue Element im Durchschnitt ungefähr in der Mitte des bereits sortierten Bereichs.

Daher braucht man im Mittel etwa halb so viele Vergleiche wie im Worst Case:

[math]\displaystyle{ \frac{1}{2}\cdot\frac{n(n-1)}{2} }[/math]

Das ist ebenfalls proportional zu [math]\displaystyle{ n^2 }[/math].

Deshalb gilt auch hier:

[math]\displaystyle{ \mathcal{O}(n^2) }[/math]

Der konstante Faktor ist zwar kleiner als im Worst Case, die Komplexitätsklasse bleibt aber gleich.

Wichtige Erkenntnis

Bei der Groß-O-Notation interessieren nur:

• das grundsätzliche Wachstum,
• die höchste Potenz.

Konstanten werden ignoriert.

Beispiele:

• [math]\displaystyle{ 3n }[/math] → [math]\displaystyle{ \mathcal{O}(n) }[/math]
• [math]\displaystyle{ \frac{1}{2}n^2 }[/math] → [math]\displaystyle{ \mathcal{O}(n^2) }[/math]

Deshalb können zwei Algorithmen unterschiedlich schnell sein, aber trotzdem dieselbe Komplexitätsklasse besitzen.