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: [math]\displaystyle{ f(x)=1/x+x }[/math]

Die rot dargestellte Funktion[math]\displaystyle{ \color{Red}{f(x) = 1/x + x} }[/math]nähert sich für große x der grün dargestellte Asymptote [math]\displaystyle{ \color{green}{g(x)} }[/math] 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. 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.