O-Notation

Einführung

Die Laufzeit eines Algorithmus beschreibt das Wachstum der Ausführungszeit in Abhängigkeit von der Eingabegröße. Die grundlegende Zuordnungsfunktion lautet dabei: > Laufzeit $\rightarrow$ Eingabegröße (siehe Grafik)

In der Informatik interessiert man sich bei der Analyse von Algorithmen meist nicht für die exakte Funktionsvorschrift (inklusive aller Konstanten und kleineren Terme), sondern primär für die „Größenordnung“ in Form des dominantesten Terms (der höchsten Potenz). Die formale Notation hierfür nennt sich O-Notation (oft auch Landau-Notation oder Big-O-Notation genannt).

Das Laufzeitverhalten von Algorithmen erschließt sich über die Anzahl der Kernoperationen. Kernoperationen sind elementare Arbeitsschritte, die maßgeblich charakteristisch für die Gesamtlaufzeit des Algorithmus sind.

Beispiele für Komplexitätsklassen

Die folgende Tabelle zeigt verschiedene mathematische Funktionen, deren Wachstumsverhalten und die daraus resultierende Komplexitätsklasse in der O-Notation. Bei der Bildung der O-Notation fallen konstante Vorfaktoren sowie unbedeutendere Summanden weg.

Funktion	Wachstum	O-Notation
[math]\displaystyle{ 32 + 5 \cdot 45 }[/math]	konstant	[math]\displaystyle{ \mathcal{O}(1) }[/math]
[math]\displaystyle{ 2 \cdot \log_4(n) + 4 }[/math]	logarithmisch	[math]\displaystyle{ \mathcal{O}(\log n) }[/math]
[math]\displaystyle{ 0{,}6 \cdot n + 3{,}4 }[/math]	linear	[math]\displaystyle{ \mathcal{O}(n) }[/math]
[math]\displaystyle{ 5 \cdot n^2 + 4 \cdot n }[/math]	quadratisch	[math]\displaystyle{ \mathcal{O}(n^2) }[/math]
[math]\displaystyle{ 9 \cdot n^7 + 6 \cdot n^5 }[/math]	polynomial	[math]\displaystyle{ \mathcal{O}(n^7) }[/math]
[math]\displaystyle{ 15 \cdot 8^n + 3 \cdot n^2 }[/math]	exponentiell	[math]\displaystyle{ \mathcal{O}(8^n) }[/math]

Grafische Darstellung der Laufzeiten

Das folgende Diagramm veranschaulicht, wie sich die benötigte Zeit (Laufzeit) bei steigender Eingabemenge (Space/n) in den unterschiedlichen Komplexitätsklassen verhält.