Asymptotische Laufzeit
In der theoretischen Informatik, speziell in der Komplexitätstheorie, bezeichnet die asymptotische Laufzeit die Anzahl der Schritte, die ein abstrakter Automat (z.B. eine Turingmaschine) zur Ausführung eines Algorithmus bei gegebener Eingabe benötigt, bis ein Endzustand erreicht und eine Ausgabe fertig berechnet ist. Die Laufzeit wird oft in Abhängigkeit von der Größe der Eingabe angegeben und für große asymptotisch unter Verwendung des Landau-Symbols abgeschätzt.Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:
- Die worst case-Laufzeit (engl schlechtester Fall) gibt an, wie lang der Algorithmus maximal braucht. Für viele Algorithmen gibt es nur wenige Eingaben, die diese worst case-Laufzeit erreichen, weshalb sie nicht unbedingt eine realistische Abschätzung ist. Handelt es sich aber um Echtzeit-Systeme, so muss die worst case-Laufzeit natürlich berücksichtigt werden.
- Die average case-Laufzeit (engl. durchschnittlicher Fall) gibt die erwartete Laufzeit bei einer Gleichverteilung der Eingaben an. Da man allerdings bei realen Programmen selten von der Gleichverteilung der Eingaben ausgehen kann, ist auch diese Abschätzung nur bedingt nutzbar.
- Die best case-Laufzeit (engl. bester Fall) gibt an, wie lang der Algorithmus in jedem Fall braucht, also selbst für die Eingaben, auf denen er ideal arbeitet. Diese untere Schranke zur Lösung des Problems wird nur recht selten angegeben, da sie nur für wenige Fälle zutrifft und die best case-Laufzeit natürlich in der für die schlechteren Fälle enthalten ist.
- Für eine realistische Abschätzung der Laufzeit eignet sich bei komplexen Algorithmen die amortisierte Analyse, die die Kosten des Algorithmus über die komplette Verarbeitung betrachtet und nicht nur die Kosten einzelnen Schritte. Bei Fibonacci-Heaps beispielsweise gibt es zwar Sortieroperationen, die teuer sein können, aber diese kommen nur einmal beim Durchlauf des Algorithmus vor, in allen folgenden Schritten ist der Heap bereits "fast sortiert", und der Sortierschritt ist billig. Das Problem an der amortisierten Analyse ist, dass sie nicht einfach durchzuführen ist, da man zunächst eine Funktion entwickeln muss, die das Verhalten der Datenstruktur möglichst genau modelliert.