Laufzeitanalyse

Einführung

Asymptotische Annäherung einer Funktion

Die Laufzeitanalyse untersucht die sogenannte Zeitkomplexität eines Algorithmus. Man stellt sich dabei im Kern die Frage: „Wie verhält sich die Rechenzeit, wenn die Menge der zu verarbeitenden Daten extrem groß wird?“

Da die echte Ausführungszeit (in Sekunden) stark vom jeweiligen Computer abhängt, misst man stattdessen die Anzahl der elementaren Befehle (z. B. Vergleiche oder Tauschoperationen). Diese Anzahl hängt von der Größe der Eingabemenge ab, die in der Informatik meist als Problemgröße [math]\displaystyle{ n }[/math] bezeichnet wird.

Für kleine Datenmengen (z. B. eine Liste mit 10 Elementen sortieren) ist fast jeder Algorithmus schnell genug. Spannend wird es erst bei sehr großen Datenmengen (z. B. Millionen von Kundendatensätzen). Hier betrachtet man die sogenannte asymptotische Laufzeit. Sie beschreibt das Verhalten des Algorithmus, wenn die Datenmenge [math]\displaystyle{ n }[/math] theoretisch ins Unendliche wächst.

Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise: [math]\displaystyle{ f(x) = \frac{1}{x} + x }[/math]

So nähert sich die rot dargestellte Funktion [math]\displaystyle{ \color{red}{f(x)} }[/math] für große [math]\displaystyle{ x }[/math] der grün dargestellten Asymptote [math]\displaystyle{ \color{green}{g(x) = x} }[/math] an.

Die Laufzeit wird mit der sogenannten Landau-Notation (Groß-O-Notation, z. B. [math]\displaystyle{ \mathcal{O}(n^2) }[/math]) abgeschätzt. Dabei werden konstante Vorfaktoren (wie [math]\displaystyle{ \frac{1}{2} }[/math]) oder kleinere Summanden ignoriert, da bei riesigen Datenmengen nur noch der dominierende Teil der Funktion das Wachstum bestimmt.

Was die Laufzeitanalyse NICHT ist

Sie misst nicht den tatsächlichen Zeitaufwand in Millisekunden auf einem echten Computer. Sie ist ein theoretisches Modell, um Algorithmen hardwareunabhängig miteinander vergleichen zu können.

Szenarien der Laufzeitabschätzung

Da Algorithmen je nach Vorsortierung der Daten unterschiedlich schnell arbeiten, unterscheidet man drei klassische Fälle:

• Das Worst-Case-Szenario (Schlechtester Fall): Die Daten liegen so ungünstig vor, dass der Algorithmus maximal lange braucht. Dies liefert eine absolute Sicherheitsgarantie (obere Schranke).
• Das Best-Case-Szenario (Bester Fall): Die Daten liegen optimal vor (z. B. bereits sortiert). Der Algorithmus ist minimal schnell fertig.
• Das Average-Case-Szenario (Durchschnittlicher Fall): Beschreibt die zu erwartende Laufzeit bei völlig zufällig gemischten Daten. Dies ist oft das realistischste Szenario in der Praxis.

Mathematische Berechnung des Average-Case

Oft wird fälschlicherweise angenommen, der Average-Case sei einfach „die Hälfte des Worst-Case“. Das ist mathematisch ungenau. Tatsächlich berechnet man den Average-Case mit Hilfe der Stochastik: Er entspricht dem Erwartungswert der Laufzeit.

Man berechnet ihn, indem man alle möglichen Eingaben durchspielt und gewichtet. Die Formel für den Erwartungswert [math]\displaystyle{ E(T) }[/math] lautet:

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

• [math]\displaystyle{ p_i }[/math] ist die Wahrscheinlichkeit für einen bestimmten Fall [math]\displaystyle{ i }[/math].
• [math]\displaystyle{ t_i }[/math] ist die Anzahl der Rechenschritte, die der Algorithmus in diesem Fall braucht.

Für die Schule gehen wir meistens von einer Gleichverteilung aus: Jeder Fall tritt mit derselben Wahrscheinlichkeit auf.

Beispiel 1: Average-Case der Linearen Suche

Wir suchen eine bestimmte Zahl in einem Array der Länge [math]\displaystyle{ n }[/math]. Wir nehmen an, die Zahl ist im Array und jede Position ist gleich wahrscheinlich.

• Schritt 1: Wahrscheinlichkeit bestimmen. Die Wahrscheinlichkeit, dass unsere Zahl an Position 1, 2 oder [math]\displaystyle{ n }[/math] steht, ist jeweils [math]\displaystyle{ p = \frac{1}{n} }[/math].
• Schritt 2: Schritte zählen. Steht die Zahl an Position 1, brauchen wir 1 Vergleich. An Position 2 brauchen wir 2 Vergleiche. An Position [math]\displaystyle{ n }[/math] brauchen wir [math]\displaystyle{ n }[/math] Vergleiche.
• Schritt 3: Erwartungswert berechnen. Wir setzen dies in die Formel ein:

[math]\displaystyle{ E(T) = \frac{1}{n}\cdot 1 + \frac{1}{n}\cdot 2 + \dots + \frac{1}{n}\cdot n = \sum_{i=1}^{n} \left( \frac{1}{n} \cdot i \right) }[/math]

Wir klammern [math]\displaystyle{ \frac{1}{n} }[/math] aus:

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

Die Summe der Zahlen von 1 bis [math]\displaystyle{ n }[/math] lässt sich mit der Gaußschen Summenformel (kleiner Gauß) vereinfachen zu [math]\displaystyle{ \frac{n(n+1)}{2} }[/math]:

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

Fazit: Im Durchschnitt braucht die lineare Suche [math]\displaystyle{ \frac{n+1}{2} }[/math] Vergleiche. Da in der [math]\displaystyle{ \mathcal{O} }[/math]-Notation Konstanten wie [math]\displaystyle{ \frac{1}{2} }[/math] wegfallen, gehört die lineare Suche im Durchschnitt zur Klasse [math]\displaystyle{ \mathcal{O}(n) }[/math].

Beispiel 2: Vorbereitung auf Quicksort (Maximumsuche)

Bei komplexeren Algorithmen wie Quicksort reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem mathematischen Trick: Indikatorvariablen und der Harmonischen Reihe. Um das zu verstehen, analysieren wir einen simplen Code zur Maximumsuche:

public int findMax(int[] A) {
    int max = A[0];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > max) {
            max = A[i]; // Update-Operation
        }
    }
    return max;
}

Die Vergleiche in der if-Bedingung werden immer [math]\displaystyle{ n-1 }[/math] Mal ausgeführt. Aber wie oft wird die Variable max im Durchschnitt überschrieben (Update-Operation)?

Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.

• Intuitiver Ansatz:

Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1). Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist exakt 50% ([math]\displaystyle{ \frac{1}{2} }[/math]). Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist [math]\displaystyle{ \frac{1}{3} }[/math].

• Mathematischer Ansatz (Indikatorvariablen):

Wir definieren einen „Schalter“ (die Indikatorvariable) [math]\displaystyle{ X_i }[/math]. Er ist [math]\displaystyle{ 1 }[/math], wenn ein neues Maximum an Stelle [math]\displaystyle{ i }[/math] gefunden wird, sonst [math]\displaystyle{ 0 }[/math]. Die Wahrscheinlichkeit dafür ist [math]\displaystyle{ P(X_i = 1) = \frac{1}{i} }[/math].

Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:

[math]\displaystyle{ E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n} }[/math]

Diese spezielle Summe nennt man in der Mathematik die Harmonische Reihe ([math]\displaystyle{ H_n }[/math]). Sie wächst extrem langsam. Für große Zahlen [math]\displaystyle{ n }[/math] entspricht sie in etwa dem natürlichen Logarithmus ([math]\displaystyle{ \ln(n) }[/math]).

Erkenntnis für Quicksort: Obwohl das Array [math]\displaystyle{ n }[/math] Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft ([math]\displaystyle{ \mathcal{O}(\log n) }[/math]) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um später selbst zu beweisen, dass Quicksort im Average-Case bei [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] liegt.

Beispiel 3: Laufzeitanalyse von Insertion Sort

Nun wenden wir unser Wissen auf das Sortierverfahren Insertion Sort (Sortieren durch Einfügen) an.

public void sortierenEinfuegen_MC() {
    int v, i, j;
    for (i = 1; i < zSortfeld.length; i++) {
        c++; // Zähler für Vergleiche
        if (zSortfeld[i] < zSortfeld[i - 1]) {
            v = zSortfeld[i];
            j = i;
            do {
                zSortfeld[j] = zSortfeld[j - 1];
                j--;
            } while ((j > 0) && (zSortfeld[j - 1] > v));
            zSortfeld[j] = v; 
        }
        printAnalyse(i);
    }
}

Wir analysieren eine Liste mit [math]\displaystyle{ n }[/math] Elementen. Den Zeitverbrauch für einen einzelnen Vergleich nennen wir [math]\displaystyle{ c }[/math].

1. Best-Case-Szenario (Bester Fall)

Die Liste ist bereits perfekt aufsteigend sortiert (z. B. [0, 2, 3, 5, 7]).

• Verhalten: Da jedes Element schon größer als sein Vorgänger ist, ist die if-Bedingung immer falsch. Die innere do-while-Schleife wird ignoriert.
• Aufwand: Wir machen exakt einen Vergleich pro Element in der äußeren Schleife. Das ergibt [math]\displaystyle{ c \cdot (n - 1) }[/math] Vergleiche.
• Komplexität: Der Aufwand wächst wie eine Gerade (linear). Die Komplexität ist [math]\displaystyle{ \mathcal{O}(n) }[/math].

2. Worst-Case-Szenario (Schlechtester Fall)

Die Liste ist exakt falsch herum sortiert (z. B. [7, 5, 3, 2, 0]).

• Verhalten: Die if-Bedingung ist immer wahr. Jedes Element muss durch die innere Schleife komplett bis an den Anfang der Liste getauscht werden.
• Aufwand: Beim 1. Durchlauf machen wir 1 Vergleich. Beim 2. Durchlauf 2 Vergleiche. Beim letzten Durchlauf [math]\displaystyle{ n-1 }[/math] Vergleiche. Wir müssen also wieder addieren: [math]\displaystyle{ 1 + 2 + 3 + \dots + (n-1) }[/math].

Wie bei der linearen Suche hilft uns hier die Gaußsche Summenformel: [math]\displaystyle{ c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n }[/math]

Quadratisches Wachstum

• Komplexität: Für extrem große [math]\displaystyle{ n }[/math] dominiert das [math]\displaystyle{ n^2 }[/math] alles andere. Wir ignorieren den Faktor [math]\displaystyle{ \frac{c}{2} }[/math] und den kleineren Teil [math]\displaystyle{ n }[/math]. Das Wachstum ist quadratisch, also [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

3. Average-Case-Szenario (Durchschnittlicher Fall)

Die Werte im Array sind völlig zufällig verteilt.

• Verhalten: Im Durchschnitt müssen wir ein Element nicht bis ganz an den Anfang schieben (wie im Worst-Case), sondern nur bis zur Hälfte des bisher sortierten Bereichs.
• Aufwand: Die Anzahl der Vergleiche halbiert sich grob im Vergleich zum Worst-Case. Der Aufwand liegt bei ca. [math]\displaystyle{ \frac{1}{2} \cdot \frac{c}{2}n^2 }[/math].
• Komplexität: Wie wir gelernt haben, ignoriert die Groß-O-Notation konstante Brüche (wie [math]\displaystyle{ \frac{1}{4} }[/math]). Es bleibt bei der höchsten Potenz: Das Wachstum ist und bleibt quadratisch. Die Komplexität lautet also weiterhin [math]\displaystyle{ \mathcal{O}(n^2) }[/math].