prev up next

Previous: Komplexität, Verifikation, Terminierung Up: Komplexität, Verifikation, Terminierung Next: Analyse von for-Schleifen

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


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

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
$log(n)$ 2.3 $\mu$s 3.0 $\mu$s 4.9 $\mu$s 5.3 $\mu$s 5.6 $\mu$s 5.9 $\mu$s
$ n $ 10 $\mu$s 20 $\mu$s 30 $\mu$s 40 $\mu$s 50 $\mu$s 60 $\mu$s
$n\cdot log(n)$ 23 $\mu$s 60 $\mu$s 147 $\mu$s 212 $\mu$s 280 $\mu$s 354 $\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


Unterabschnitte
prev up next
Previous: Komplexität, Verifikation, Terminierung Up: Komplexität, Verifikation, Terminierung Next: Analyse von for-Schleifen