Was ist Zeitkomplexität (O-Notation)?
Beschreibung, wie der Aufwand (Zeitkomplexität) oder der Speicherbedarf (Platzkomplexität) eines Algorithmus mit der Zahl n der Datenelemente wächst. Angegeben wird sie in O-Notation, etwa O(n), O(n log n) oder O(n²), wobei konstante Faktoren und Terme niedrigerer Ordnung entfallen.
Japanische Bezeichnung: 計算量
„Zeitkomplexität (O-Notation)“ kommt in 3 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.
Fachgebiet: Datenstrukturen und Algorithmen
O-Notation lesen
O(f(n)) bedeutet, dass der Aufwand für ausreichend große n innerhalb eines konstanten Vielfachen von f(n) bleibt. Ein Algorithmus mit 3n² + 5n + 2 Vergleichen wird als O(n²) geschrieben, weil mit wachsendem n der Term n² dominiert. Gängige Klassen sind in aufsteigender Reihenfolge O(1) (konstant), O(log n) (binäre Suche), O(n) (lineare Suche), O(n log n) (Mergesort, Heapsort), O(n²) (Bubblesort, Selectionsort) und O(2ⁿ) (naive erschöpfende Suche). Für n = 1000 beträgt log₂ n etwa 10, n log₂ n etwa 10.000 und n² genau 1 Million; bei großen Datenmengen ist der Unterschied in der Komplexität daher entscheidend.
Bester, mittlerer und schlechtester Fall
Derselbe Algorithmus kann je nach Eingabe unterschiedlich viel Arbeit leisten. Insertionsort braucht bei sortierten Daten n−1 Vergleiche, also O(n), bei umgekehrt sortierten Daten aber n(n−1)/2, also O(n²). Quicksort ist im Mittel O(n log n), je nach Pivotwahl und Daten im schlechtesten Fall aber O(n²). Systeme, die eine obere Schranke für die Antwortzeit brauchen, achten auf den schlechtesten Fall, während Schätzungen des Gesamtdurchsatzes den mittleren Fall verwenden. Gleicht sich ein gelegentlicher teurer Schritt über viele Operationen zu einem konstanten Aufwand aus, wie beim Anfügen an ein dynamisches Array, spricht man von amortisiert O(1).
Die tatsächliche Geschwindigkeit hängt nicht nur von der Komplexität ab
Da die O-Notation konstante Faktoren ignoriert, können sich zwei O(n)-Algorithmen in der tatsächlichen Geschwindigkeit stark unterscheiden. Auf heutigen Computern ist der Hauptspeicher fast 100-mal langsamer als der L1-Cache, daher ist das sequenzielle Lesen eines Arrays um ein Vielfaches schneller als das Durchlaufen einer verketteten Liste. Bei kleinem n kann zudem ein einfacher Algorithmus mit schlechterer Komplexität schneller sein, weshalb praktische Sortierimplementierungen für kurze Bereiche Insertionsort verwenden. Bei der Leistungsverbesserung prüft man zuerst, ob kein Algorithmus mit unnötig hoher Komplexität verwendet wird, und misst und verfeinert dann Details wie die Muster der Speicherzugriffe.
Häufige Fragen
Welche Basis hat der Logarithmus in O(log n)?
Ein Wechsel der Basis ändert den Wert nur um einen konstanten Faktor (log₂ n = log₁₀ n ÷ log₁₀ 2), daher lässt die O-Notation die Basis üblicherweise weg. Bei Algorithmen, die die Daten in jedem Schritt halbieren, wie der binären Suche, liegt die tatsächliche Anzahl nahe bei log₂ n.
Was ist der Unterschied zwischen Zeitkomplexität und Platzkomplexität?
Die Zeitkomplexität beschreibt, wie der Aufwand (die Laufzeit) wächst, die Platzkomplexität, wie der benötigte Speicher wächst. Beide werden zusammen verglichen: Mergesort hat die Zeitkomplexität O(n log n) bei O(n) Arbeitsspeicher, Heapsort O(n log n) bei O(1) Speicher.