Zeitkomplexität

Grundidee und Bedeutung

Zeitkomplexität bezeichnet in der Informatik die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung einer Aufgabe benötigt, abhängig von der Länge der Eingabe. Sie wird auch asymptotische Laufzeit genannt: Untersucht wird, wie sich der Aufwand bei sehr großen Eingabemengen verhält.

Entscheidend ist nicht die konkrete Laufzeit eines Programms auf einem bestimmten Computer. Stattdessen betrachtet man die Skalierbarkeit: Wie wächst der Zeitbedarf, wenn mehr Daten verarbeitet werden? Bei doppelter Datenmenge kann sich der Aufwand zum Beispiel verdoppeln oder quadrieren.

Die Laufzeit wird in Abhängigkeit von der Eingabelänge n angegeben und für immer größer werdende n mit der Landau-Notation, insbesondere der Groß-O-Notation, abgeschätzt. Rekursionsgleichungen lassen sich genauer etwa mit dem Mastertheorem oder der Substitutionsmethode abschätzen.

Algorithmen, Probleme und Modelle

Bei einem konkreten Algorithmus ist mit Zeitkomplexität die Zahl der Schritte für eine Eingabe der Länge n gemeint. Sie kann für den besten, schlechtesten oder durchschnittlichen Fall bestimmt werden.

In der Komplexitätstheorie stehen jedoch Probleme im Mittelpunkt. Die Komplexität von Algorithmen ist vor allem wichtig, weil sie Aussagen über die Schwierigkeit des behandelten Problems ermöglicht. Zeitkomplexität gehört dort neben der Platzkomplexität, also dem benötigten Speicherplatz, zu den am häufigsten untersuchten Eigenschaften. Sie bildet unter anderem eine Grundlage für bedeutsame Komplexitätsklassen.

Praktisch hilft die Analyse bei der Auswahl eines passenden Algorithmus. Bubblesort ist bei großen Datenmengen recht langsam, kann wegen seines geringen Overheads aber für kleine Datenmengen geeignet sein, insbesondere für n ≤ 8.

Zeitkomplexität wird stets bezogen auf ein Maschinenmodell angegeben. Üblich ist die Turingmaschine; alternativ kann eine Registermaschine verwendet werden, die tatsächlichen Computern ähnlicher ist. Für parallele Algorithmen eignet sich ein paralleles Modell wie PRAM. Mit PRAM steht das Externspeichermodell in Beziehung; Probleme, die effizient im PRAM lösbar sind, können auch effizient im Externspeicher berechnet werden. Außerdem unterscheidet man deterministische und nichtdeterministische Maschinen.

Best-, Worst- und Average-Case

Wenn neben der Eingabelänge weitere Faktoren die Laufzeit stark beeinflussen, werden verschiedene Fälle unterschieden:

• Die worst-case-Laufzeit ist die maximale Laufzeit. Nur wenige Eingaben erreichen sie möglicherweise, daher ist sie nicht immer realistisch. In Echtzeitsystemen muss sie aber berücksichtigt werden.
• Die average-case-Laufzeit ist die erwartete Laufzeit für eine gegebene Verteilung der Eingaben. Ist diese Verteilung unbekannt, lässt sie sich nur unter einschränkenden Annahmen berechnen. Dazu passt auch die amortisierte Laufzeitanalyse.
• Die best-case-Laufzeit ist die minimale Laufzeit, also die Laufzeit bei idealen Eingaben. Sie wird selten angegeben, weil sie nur für wenige Fälle gilt und in den Angaben zu schlechteren Fällen bereits enthalten ist.

Wenn lediglich von Zeitkomplexität gesprochen wird, ist meistens die Abschätzung für den worst case gemeint.

Abhängigkeit von Operationen und Datenstrukturen

Oft wird Zeitkomplexität nicht unmittelbar in Zeit, sondern in der Anzahl bestimmter Operationen angegeben. Bei Sortieralgorithmen zählt man beispielsweise Vergleichsoperationen und nimmt an, dass jeder Vergleich konstante Zeit benötigt. Für elementare Datentypen gilt das normalerweise, für Zeichenketten jedoch nicht unbedingt. Vergleicht man Algorithmen mit ähnlichen Vergleichen, bleibt das Ergebnis dennoch aussagekräftig.

DBSCAN führt für jeden Punkt genau eine Nachbarschaftsanfrage aus. Da sie als langsamste Operation gilt, wird DBSCAN als linear in der Anzahl der Nachbarschaftsanfragen bezeichnet. Für den Vergleich mit einem Algorithmus ohne solche Anfragen ist jedoch ein anderes Maß nötig. Die Geschwindigkeit einer Nachbarschaftsanfrage hängt von der Indexstruktur ab, ohne dass DBSCAN selbst verändert wird. Ohne Index-Unterstützung besitzt DBSCAN eine quadratische Zeitkomplexität in der Anzahl der Distanzberechnungen.

Beispiel einer Listensuche und amortisierte Analyse

Bei einer Liste mit zwanzig Namen wird von vorn gesucht, bis der eingegebene Name gefunden ist. Im best case steht der Name an erster Stelle; die Suchzeit ist 1. Im worst case steht er an letzter Stelle; die Suchzeit ist 20. Dieselbe Suchzeit entsteht, wenn der Name nicht in der Liste ist. Ist der Name sicher enthalten, beträgt der average case 10,5.

Für komplexe Algorithmen kann die amortisierte Analyse eine realistischere Abschätzung liefern. Sie betrachtet die durchschnittlichen Kosten über alle möglichen Eingaben und berücksichtigt, wie wahrscheinlich einzelne Fälle sind. Beim Sortieren mit einem Fibonacci-Heap kann das Einsortieren eines neuen Eintrags im schlechtesten Fall aufwändig sein. Solche Fälle treten beim Durchlauf des Gesamtalgorithmus aber nur einmal auf; danach ist der Heap „fast sortiert“ und der einzelne Schritt billig. Die Analyse ist schwierig, weil zunächst eine Funktion entwickelt werden muss, die das Verhalten der Datenstruktur und damit die Wahrscheinlichkeit der Fälle möglichst genau modelliert.

In der Informationstheorie dient Zeitkomplexität dazu, die Algorithmische Tiefe einer Datenmenge zu bestimmen.