Unter der Zeitkomplexität eines Problems versteht man die (minimale) Anzahl an Rechenschritten, die ein geeigneter Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe, also die asymptotische Laufzeit. Es interresiert als nicht der Zeitaufwand eines konkreten Programmes auf einem bestimmten Computer (Performanz), sonden viel mehr, wie der Zeitbedarf wächst wenn mehr Daten zu verarbeiten sind, also z.B. ab sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Die Laufzeit wird daher oft in Abhängigkeit von der Länge n der Eingabe angegeben und für große n asymptotisch unter Verwendung des Landau-Symbols abgeschätzt.
Die Zeitkomplexität wird immer in Bezug auf ein Maschinenmodell angegeben. In der Regel ist das Bezugsmodell die Turingmaschine, allerdings wird dabei zwischen Komplexitäten für deterministische und nichtdeterministische Turingmaschinen unterschieden.
In der Komplexitätstheorie ist die Zeitkomplexität neben der Platzkomplexität ein wichtiges Maß für die "Härte" (Schwierigkeit oder eben Komplexität) von Problemen. Formal werden Probleme gemäß ihrer Zeitkomplexität in Komplexitätsklassen eingeteilt.
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.
In der Informationstheorie wird die Zeitkomplexität verwendet, um die Algorithmische Tiefe einer Datenmenge zu bestimmen.
Siehe auch: Platzkomplexität, Komplexität (Informatik)