Laufzeitanalyse

Einführung

Die Laufzeitanalyse betrachtet die Zeitkomplexität eines Algorithmus. Da die reale Ausführungszeit stark von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine, hardwareunabhängige Betrachtung die Anzahl der Befehle (Operationen) analysiert, die ein Algorithmus zur Lösung eines Problems benötigt. Diese Anzahl ist abhängig von der Eingabe, deren Umfang auch als Problemgröße (oft [math]\displaystyle{ n }[/math]) bezeichnet wird.

Für kleine Eingabemengen ist die Analyse häufig von geringerer Bedeutung, da auch ineffiziente Algorithmen hier oft befriedigend schnelle Ergebnisse liefern. Entscheidend ist die Betrachtung für sehr große Problemgrößen, insbesondere unter ungünstigen Startbedingungen (Worst-Case). Hier spricht man von der asymptotischen Laufzeit. In Anlehnung an eine mathematische Asymptote beschreibt sie das Zeitverhalten des Algorithmus für eine potenziell unendlich wachsende Eingabemenge (z. B. eine theoretisch unendlich lange Zahlenfolge beim Sortieren).

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 in Abhängigkeit von der Länge [math]\displaystyle{ n }[/math] der Eingabe angegeben und für immer größer werdende [math]\displaystyle{ n }[/math] asymptotisch unter Verwendung der Landau-Notation (Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse essenziell, um entscheiden zu können, ob ein Programm bei stark anwachsenden Datenmengen noch performant und wirtschaftlich betrieben werden kann.

Abgrenzung

Es ist wichtig zu betonen, was die asymptotische Laufzeitanalyse nicht leistet: Sie misst nicht den tatsächlichen Zeitaufwand (in Sekunden) eines implementierten Algorithmus auf einem spezifischen Computer für eine konkrete, endliche Eingabemenge.

Szenarien

Man unterscheidet bei der Laufzeitabschätzung klassischerweise drei Varianten:

• Das Worst-Case-Szenario (schlechtester Fall): Beschreibt die Startanordnung der Daten, die zu einer maximalen Durchlaufzeit des Algorithmus führt. Dies entspricht der oberen Schranke des Problems.
• Das Average-Case-Szenario (durchschnittlicher Fall): Beschreibt die Problemgröße und Datenanordnung, die zu einer mittleren (erwarteten) Durchlaufzeit führt.
• Das Best-Case-Szenario (bester Fall): Beschreibt die Datenanordnung, die zu einer minimalen Durchlaufzeit führt (z. B. eine bereits sortierte Liste). Dies entspricht der unteren Schranke.

Beispiel: Laufzeitanalyse von Insertion Sort

Im Folgenden wird die Laufzeitanalyse beispielhaft anhand des Insertion Sorts durchgeführt. Wir betrachten eine mögliche Implementierung in der Programmiersprache Java. Der Algorithmus arbeitet mit einem Array als Datenstruktur und verwendet als Kontrollstrukturen Verzweigungen und Schleifen.

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);
    }
}

Ein Worst-Case-Szenario für den Insertion Sort ist eine Liste, die in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise: [11, 7, 5, 3, 2, 0]

Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Wir bezeichnen diesen konstanten Zeitverbrauch für einen einzelnen Vergleich allgemein mit [math]\displaystyle{ c }[/math]. Die Anzahl der zu sortierenden Elemente sei [math]\displaystyle{ n }[/math].

• Beim ersten Durchlauf der äußeren Schleife vergleichen wir nur die 7 mit der 11. Aufwand: [math]\displaystyle{ c \cdot 1 }[/math]. Die 7 wird einsortiert.
• Beim zweiten Durchlauf müssen wir das nächste Element mit den beiden bereits sortierten Elementen vergleichen. Aufwand: [math]\displaystyle{ c \cdot 2 }[/math].
• Dies setzt sich fort bis zum letzten Durchlauf, der [math]\displaystyle{ n - 1 }[/math] Vergleiche erfordert. Aufwand: [math]\displaystyle{ c \cdot (n - 1) }[/math].

Der Gesamtaufwand für die Vergleiche lautet also: [math]\displaystyle{ c \cdot (1 + 2 + 3 + \dots + (n - 1)) }[/math]

Hierbei handelt es sich um eine arithmetische Reihe (angelehnt an den Gaußschen Summensatz), die bis [math]\displaystyle{ n - 1 }[/math] läuft. Unter Verwendung der entsprechenden Summenformel erhalten wir:

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

Für die asymptotische Betrachtung extrem großer Werte von [math]\displaystyle{ n }[/math] verwerfen wir den langsamer wachsenden (niederwertigen) Term [math]\displaystyle{ \frac{c}{2}n }[/math] sowie die Konstante [math]\displaystyle{ \frac{c}{2} }[/math]. Daraus folgt:

Für sehr große [math]\displaystyle{ n }[/math] verhält sich der Aufwand [math]\displaystyle{ C(n) }[/math] asymptotisch wie [math]\displaystyle{ n^2 }[/math]. Anders ausgedrückt: [math]\displaystyle{ C(n) }[/math] liegt in der Komplexitätsklasse [math]\displaystyle{ \mathcal{O}(n^2) }[/math].

Einfluss weiterer Operationen (Lesen/Schreiben): Wie beeinflussen Lese- und Schreiboperationen (das Verschieben der Werte) die Zeitkomplexität? Für das Verschieben käme lediglich ein konstanter Aufwand je Vergleich hinzu. Nennen wir diesen Aufwand [math]\displaystyle{ v }[/math]. Die angepasste Funktion lautet dann:

[math]\displaystyle{ \frac{v+c}{2}n^2 - \frac{v+c}{2}n }[/math]

Auch hier gilt: Für sehr große [math]\displaystyle{ n }[/math] können der niederwertige Term [math]\displaystyle{ \frac{v+c}{2}n }[/math] und der konstante Faktor [math]\displaystyle{ \frac{v+c}{2} }[/math] ignoriert werden. Es bleibt bei der Erkenntnis: Das Laufzeitverhalten [math]\displaystyle{ C(n) }[/math] liegt asymptotisch weiterhin in der Klasse [math]\displaystyle{ \mathcal{O}(n^2) }[/math].