Asymptotische Laufzeit

Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen Laufzeit und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z. B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Die Laufzeit wird daher 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. Eine genauere Laufzeitabschätzung von Rekursionsgleichungen bietet auch das Mastertheorem oder die Substitutionsmethode.

Bezieht man den Begriff der Zeitkomplexität auf einen konkreten Algorithmus, so ist damit die Anzahl der Schritte gemeint, die der Algorithmus für die Bearbeitung einer Eingabe mit bestimmter Länge n benötigt (im besten, schlechtesten oder durchschnittlichen Fall, siehe unten). In der Komplexitätstheorie ist der eigentliche Gegenstand der Betrachtung aber die Komplexität von Problemen. Die Komplexität von Algorithmen ist nur insofern interessant, als man daraus Aussagen über das behandelte Problem schließen kann. In der Praxis ist diese aber häufig interessant, vor allem um für einen konkreten Kontext einen geeigneten Algorithmus auszuwählen: So ist Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet sich aber aufgrund des geringen Overheads gut für kleine Datenmengen (insbesondere für n ≤ 8).

Die Zeitkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine, alternativ kann die Zeitkomplexität aber auch in Bezug auf eine Registermaschine angegeben werden, die in ihrem Verhalten mehr den tatsächlich existierenden Computern ähnelt. Für parallele Algorithmen kann ein paralleles Maschinenmodell wie die PRAM verwendet werden. Zudem wird zwischen der Komplexität für deterministische und nichtdeterministische Maschinen unterschieden.

In der Komplexitätstheorie ist die Zeitkomplexität neben der Platzkomplexität der am häufigsten untersuchte Aspekt von Algorithmen und Problemen. Die Zeitkomplexität aller Algorithmen, die ein Problem lösen, liegt beispielsweise einer Reihe bedeutsamer Komplexitätsklassen zu Grunde.

Varianten

Man unterscheidet die folgenden Varianten zur Laufzeitabschätzung:

• Die worst-case-Laufzeit (engl. schlechtester Fall) gibt an, wie lange 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 Echtzeitsysteme, so muss die worst-case-Laufzeit natürlich berücksichtigt werden.
• Die average-case-Laufzeit (engl. durchschnittlicher Fall) gibt die erwartete Laufzeit bei einer gegebenen Verteilung der Eingaben an. Da allerdings die Verteilung der Eingaben bei Programmen nicht immer bekannt ist, ist die Berechnung der average-case-Laufzeit in diesen Fällen nur unter einschränkenden Annahmen möglich. Siehe auch: Amortisierte Laufzeitanalyse
• Die best-case-Laufzeit (engl. bester Fall) gibt an, wie lange 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 selten angegeben, da sie nur für wenige Fälle zutrifft und die best-case-Laufzeit in der für die schlechteren Fälle enthalten ist.

Beispiel

In einer Liste werden zwanzig Namen gespeichert. Es soll nun ein vorhandener Name eingegeben und verglichen werden. Die Liste wird beginnend mit dem ersten Eintrag durchsucht bis der Name gefunden ist.

• best case: Der gesuchte Name ist der erste in der Liste, die Suchzeit ist 1.
• worst case: Der gesuchte Name ist der letzte in der Liste, Die Suchzeit ist 20. Diese Suchzeit würde sich auch einstellen, wenn der Name nicht in der Liste wäre.
• average case: Ist der Name definitiv in der Liste, beträgt der average case 10.

Spricht man einfach von Zeitkomplexität, so ist meistens die Abschätzung für den worst case gemeint.

Für eine realistische Abschätzung der Laufzeit eignet sich bei komplexen Algorithmen die amortisierte Analyse, die die durchschnittlichen Kosten des Algorithmus für alle möglichen Eingaben betrachtet, statt nur für den besten/schlechtesten/gleichverteilten Fall. Dabei ist entscheidend, wie wahrscheinlich es ist, dass ein bestimmter Fall eintritt. Diese Art der Untersuchung eignet sich besonders, wenn man den Aufwand einer Teiloperation eines größeren Algorithmus betrachtet: Beim Sortieren mittels eines Fibonacci-Heaps beispielsweise ist die Operation des Einsortierens eines neuen Eintrags zwar im schlechtesten Fall recht aufwändig, aber diese kommen nur einmal beim Durchlauf des Gesamtalgorithmus vor, in allen folgenden Schritten ist der Heap bereits „fast sortiert“, und der einzelne Schritt 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 und damit angibt, wie wahrscheinlich die einzelnen Fälle sind.

In der Informationstheorie wird die Zeitkomplexität verwendet, um die Algorithmische Tiefe einer Datenmenge zu bestimmen.

Siehe auch

• Platzkomplexität
• P-NP-Problem
• NP (Komplexitätsklasse)
• Polynomialzeit
• Effizienz

Weblinks

• Vorlesungsreihe zur "Komplexitätstheorie", Prof. Dr. Christoph Meinel, Hasso-Plattner-Institut (Sommersemester 2009)