Laufzeitanalyse

Einführung

Die Laufzeitanalyse betrachtet die Zeitkomplexität eines Algorithmus. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der Befehle analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.

Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte Algorithmen befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen Laufzeit gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen sortiert werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.

Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: f(x)=1/x+x

Die rot dargestellte Funktion f(x)=1/x+x nähert sich für große x der grün dargestellte Asymptote g(x) an.

Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.

In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.

$f(x) = \tfrac{1}{x}+x$

Abgrenzung

Abgrenzend kann gesagt werden, dass die Laufzeitanalyse folgendes nicht betrachtet:

Den Zeitaufwand eines implementierten Algorithmus auf einem bestimmten Computer für eine konkrete endliche Eingabemenge.

Szenarien

Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

Das worst-case-szenario (engl. schlechtester Fall) beschreibt die Problemgröße, die zu einer maximal langen Durchlaufzeit eines Algorithmus führt und entspricht der oberen Schranke zur Lösung eines Problems.
Das average-case-Szenario (engl. durchschnittlicher Fall) beschreibt die Problemgröße die zu einer mittleren Durchlaufzeit eines Algorithmus führt.
Das best-case-Szenario (engl. bester Fall) beschreibt die Problemgröße die zu einer minimalen Durchlaufzeit eines Algorithmus führt. Dies entspricht der untere Schranke zur Lösung eines Problems.

Beispiel

Im Folgenden wird die Laufzeitanalyse anhand des Insertionsorts praktisch durchgeführt. Wir betrachten den Insertionsort anhand einer möglichen 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;

int i;

int j;

for (i = 1; i < zSortfeld.length; i++) {

c++;

if (zSortfeld[i] < zSortfeld[i - 1]) {

v = zSortfeld[i];

j = i;

do {

zSortfeld[j] = zSortfeld[j - 1];

j--;

if (j>0) {

}

} while ((j > 0) && (zSortfeld[j - 1] > v));

zSortfeld[j] = v;

}

printAnalyse(i);

}

Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort:

[11,7,5,3,2,0]

Wir betrachten zunächst nur den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Diesen Zeitverbrauchen kennen wir nicht und geben ihn allgemein durch die Konstante c an. Die Anzahl der zu sortierenden Elemente entspricht der Variablen n.

Beim ersten äußeren Schleifendurchlauf gilt für den Zeitaufwand c*1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe InsertionSort) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche, c * 2. Beim dritte Mal, c * 3 bis zum letzten Mal, wenn c * n-1. Es gilt also:

c⋅*(1+2+3+⋯+(n−1))

Hierbei handelt es sich um eine arithmetische Reihe, mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für arithmetische Reihen, erhalten wir:

c⋅*(n−1+1)*((n−1)/2)=c*n2/2 − c*n/2

Für sehr große n können wir den niederwertigen Term n/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt:

Für sehr große n verhält sich C(n) asymptotisch wie n2. Oder anders ausgedrückt C(n) liegt in der Klasse O(n2).

Und wie beeinflussen die anderen Operationen wie Lesen und Schreiben, die zum Vertauschen der Werte benötigt werden die Zeitkomplexität? Für das Vertauschen der Werte würde nur ein konstanter Aufwand je Vergleich hinzukommen. Wir nennen ihn v und passen unsere Funktion entsprechend an:

(v+c) * n2/2 − (v+c)* n/2

Und wieder gilt, für sehr große n können wir den niederwertigen Term (v+c)* n/2 und die konstanten Faktoren v,c und 1/2 verwerfen, so dass immer noch gilt:

Für sehr große n verhält sich C(n) asymptotisch wie n2. Oder anders ausgedrückt C(n) liegt in der Klasse O(n2).