O-Notation, Laufzeiten

Laufzeit

Man kann den Zeitaufwand von Algorithmen nicht eindeutig bestimmen. Viel zu viele Faktoren (Hardware, parallel laufende Programme, Eingabereihenfolge, ...) spielen eine Rolle, so dass man mit normalen Mitteln niemals eine genaue und allgemeine Aussgae über die benötigte Zeit machen kann.
Es werden nun nicht mehr die benötigten Zeiten, sondern die benötigten "greifbaren" Schritte bei einer bestimmten Eingabelänge n beschrieben.
Somit können Programme in Klassen (konstant, logarithmisch, lineas, polynomial, exponentiell, u.a.) eingeteilt werden.

O-Notation

Möchten wir nun wissen, ob eine Laufzeit in eine Klasse gehört, so müssen wir ihr asymptotisches Wachstum beobachten.
Es gibt ein n₀ ≠ ∞, ab dem das Wachstumsverhalten vergleichbar ist mit der repräsentierenden Funktion der Klasse.

Wir können nun die Laufzeit folgendermaßen einteilen:

Worst Case	f(n) = Ο(g(n)) ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: \|f(n)\| ≤ c * g(n)	lim_n→∞ f(n)/g(n) = 0 oder c
Best Case	f(n) = Ω(g(n)) Omega ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: \|f(n)\| ≥ c * g(n)	lim_n→∞ f(n)/g(n) → ∞ oder c
Best Case und Worst Case	f(n) = Θ(g(n)) Theta ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: f(n) = O(g(n)) ∧ f(n) = Ω(g(n))	lim_n→∞ f(n)/g(n) = c

Die O-Notation ist eine Abschätzung der Laufzeit bei unendlich großen Eingaben. Da jedoch keine Eingabe unendlich ist, sollte man bei der Wahl von Algorithmen, die realistische Eingabelänge einbeziehen.

Beispiel:	f(n) = 10²⁰n	= O(n)
	g(n) = 10^-20n²	= O(n²)

Obwohl O(n) < O(n²), ist f(n) > g(n) bei kleinen n.

Anwendung

Es gibt folgenden Regeln zur Bestimmung der Klasse:

Addition	f(n) = n + 3	⇒ f(n) = Θ(n)	Konstante Summanden werden vernachlässigt
	f(n) = n² + 3n	⇒ f(n) = Θ(n²)	Es zählt der Summand mit dem stärkeren Wachstum
Multipikation	f(n) = 3n	⇒ f(n) = Θ(n)	Konstante Faktoren werden vernachlässigt
	f(n) = n² * 3n	⇒ f(n) = Θ(n³)	Es zählt die Summe der Exponenten

Wachstum im Vergleich: 1 < log n < √n < n < n(log n)² < n² < n^a < aⁿ

Umformen der Basen von Logerithmen: log_cb = log_ab / log_ac

O - Notation

Definition: f(n) und g(n) seien Funktionen von den natürlichen zu den reellen Zahlen.
f(n) = Ο(g(n)) ⇔ ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: |f(n)| ≤ c * g(n)
f(n) = Ω(g(n)) ⇔ ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: |f(n)| ≥ c * g(n)
f(n) = Θ(g(n)) ⇔ ∃n₀ ∈ N ∧ c > 0, ∀n ≥ n₀: f(n) = O(g(n)) ∧ f(n) = Ω(f(n))

Wichtige Laufzeiten

Tiefensuche O(V+E)

Breitensuche O(V+E)

Dijktra O(V+E)

	best case	middle case	worst case
Prim	O(E)	- - -	O(V²)
Quicksort	O(n logn)	O(n logn)	O(n²)
Bubblesort, Insertsort	O(n²)	O(n²)	O(n²)
Mergesort	O(n logn)	O(n logn)	O(n logn)

Links

Merkblatt der O-Notation von Augustin
O-Notation: Definition auf der Sortieralgorithmen-Seite
Laufzeit Fibonacci
Laufzeit reverse