O-Notation

Seien $f,g: \Bbb {N} \rightarrow \Bbb{N}$

$f$ ist höchstens von der Größenordnung $g$

in Zeichen: $f \in O(g)$

falls $n_{0},\ c\ {\in}\ {\Bbb{N}}$ existieren mit

$${\forall}\ n\ {\geq}\ n_{0}:\ f(n)\ {\leq}\ c\ \cdot\ g(n)\ .$$

Statt $f \in O(g)$ sagt man auch $f=O(g)$

$\Rightarrow$ Wegen des konstanten Faktors $c$ ist die exakte Festlegung eines Schrittes nicht erforderlich.

Beispiel:

Sei $f(n)=31 n+12 n^{2}$.

Dann ist $f \in O(n^{2})$

Natürlich gilt auch: $f \in O(n^{7})$ Die wesentlichen Klassen

$\log n$	$n$	$n\cdot \log n$	$n^{2}$	$n^{3}$	$n^{4}$	$\ldots$	$2^{n}$	$3^{n}$	$n!$
$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$	$\uparrow$			$\uparrow$		$\uparrow$
binäre	lineare	schlaues	dummes	Gleichungs-			alle		alle
Suche	Suche	Sortieren	Sortieren	system			Teil-		Permu-
				lösen			mengen		tationen

Annahme: 1 Schritt dauert 1 $\mu$s = 0.000001 s

$n=$	10	20	30	40	50	60
$n$	10 $\mu$s	20 $\mu$s	30 $\mu$s	40 $\mu$s	50 $\mu$s	60 $\mu$s
$n^2$	100 $\mu$s	400 $\mu$s	900 $\mu$s	1.6 ms	2.5 ms	3.6 ms
$n^3$	1 ms	8 ms	27 ms	64 ms	125 ms	216 ms
$2^n$	1 ms	1 s	18 min	13 Tage	36 J	366 Jh
$3^n$	59 ms	58 min	6.5 J	3855 Jh	$10^{8}$ Jh	$10^{13}$ Jh
$n!$	3.62 s	771 Jh	$10^{16}$ Jh	$10^{32}$ Jh	$10^{49}$ Jh	$10^{66}$ Jh

Für einen Algorithmus mit Laufzeit $O(2^{n})$ gilt daher:

Wächst $n$ um $1$, so wächst $2^n$ um den Faktor $2$.
Wächst $n$ um $10$, so wächst $2^n$ um den Faktor $2^{10}=1024$.
Ein 1000-mal schnellerer Computer kann eine um 10 Daten größere Eingabe in derselben Zeit bearbeiten.

Analoge Aussagen sind möglich bzgl. Speicherplatz.
Wir zählen nicht die Anzahl der Bytes, sondern betrachten das Wachstum des Platzbedarfs in Speicherplätzen in Abhängigkeit von der Größe der Eingabe.

Aussagen über Laufzeit und Platzbedarf beziehen sich auf

${\bullet}$ best case	günstigster Fall
${\bullet}$ worst case	ungünstigster Fall
${\bullet}$ average case	im Mittel