Zeitkomplexität
Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, 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.
Wird der Begriff der Zeitkomplexität auf einen konkreten Algorithmus bezogen, 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 daraus Aussagen über das behandelte Problem geschlossen werden können. 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. Ein in Beziehung zum PRAM Modell stehendes Modell ist das Externspeichermodell. Jedes Problem, welches effizient im PRAM gelöst werden kann, kann auch effizient im Externspeicher berechnet werden.[1] 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 mindestens 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.
Abhängige Zeitkomplexität
Meistens kann die Zeitkomplexität nur in Abhängigkeit von anderen Zeitkomplexitäten angegeben werden. So wird bei Sortieralgorithmen die Zeit eigentlich nicht direkt gemessen, sondern in „Vergleichsoperationen“, unter der Annahme, dass jeder solcher Vergleich eine konstante Zeit benötigt. Während das bei elementaren Datentypen normalerweise gilt, ist dies beispielsweise für Zeichenketten bereits nicht der Fall. Müssen zwei Algorithmen (in diesem Beispiel zwei Sortieralgorithmen) jedoch ähnliche Vergleiche durchführen, so ist das Ergebnis weiterhin aussagekräftig.
In manchen Fällen kann auch nur so eine definitive Aussage getroffen werden. Beispielsweise führt der Algorithmus DBSCAN für jeden Punkt genau eine Nachbarschaftsanfrage durch. Da eine Nachbarschaftsanfrage als die „langsamste“ Operation im Algorithmus gilt, sagt man auch, er ist „linear“ (in der Anzahl der Nachbarschaftsanfragen). Möchte man ihn jedoch mit einem Algorithmus vergleichen, der keine Nachbarschaftsanfragen durchführt, braucht man ein anderes Maß. Je nach einer vorhandenen Indexstruktur kann eine Nachbarschaftsanfrage jedoch unterschiedlich schnell beantwortet werden (ohne dass dies den Algorithmus DBSCAN verändern würde). Ohne Index-Unterstützung hat DBSCAN dann eine „quadratische“ Zeitkomplexität (in der Anzahl der Distanzberechnungen).
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,5.
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.
Literatur
- Knuth, Donald E.: Big Omicron and big Omega and big Theta. In: SIGACT News. Band 8, Nr. 2. ACM, April 1976, ISSN 0163-5700, S. 18–24, doi:10.1145/1008328.1008329.
Einzelnachweise
- Aus: Meyer, Sanders und Sibeyn: Algorithms for Memory Hierarchies: Advanced Lectures. Chapter 15.3, S. 335, Springer, 2003.