1.2.4 Laufzeit & 1.2.5 O-Kalkül

1.2.4 Laufzeit von Algorithmen

Definition

Laufzeit eines Algorithmus = Anzahl der ausgeführten primitiven Operationen. Eine primitive Operation entspricht einem Zeitschritt.

Die Laufzeit hängt von der Eingabegröße $n$ ab (z.B. Anzahl der Punkte). Sie ist also eine Funktion von $n$, die Laufzeitfunktion $T(n)$, etwa

$T(n) = a n^2 + bn + c\qquad\text{für Konstanten } a,b,c.$

Best, Worst, Average Case

Bei gleicher Eingabegröße kann die Laufzeit je nach konkreter Eingabe unterschiedlich sein:

Analyse	Frage	Beispiel Jarvis' March (§2.5)
Best Case	schnellste Eingabe der Größe $n$?	Hülle ist ein Dreieck: $O(n)$
Worst Case	langsamste Eingabe der Größe $n$?	alle Punkte auf der Hülle: $O(n^2)$
Average Case	Erwartungswert über eine Verteilung der Eingaben?	gleichverteilte Punkte im Quadrat: $O(n\log n)$

In der Vorlesung ist ohne Zusatz meist der Worst Case gemeint. Er ist eine Garantie.

Nur die Ordnung zählt

Die exakte Laufzeitfunktion ist oft sehr kompliziert und hängt von Details ab (Compiler, Rechner, welche Operation man wie zählt). Deshalb betrachtet man nur die Ordnung (Größenordnung):

• $T(n)=an^2+bn+c$ hat die Ordnung $n^2$.
• $T(n)=an+b$ hat die Ordnung $n$.

1.2.5 O-Kalkül (Landau-Symbole)

Benannt nach Edmund Landau (1877–1938).

Motivation: Um die Komplexität von Problemen und Algorithmen zu vergleichen, muss man Laufzeitfunktionen vergleichen. Relevant ist das asymptotische Wachstum: Wie verhalten sich $f(n)$ und $g(n)$ für große $n$? „Welche Funktion gewinnt das Rennen?“

Vorteile:

• Konstante Faktoren sind irrelevant (ob ein Schritt 2 oder 5 ns dauert, ist egal).
• Bei Polynomen zählt nur der größte Exponent.

Big-O: obere Schranke (≤)

$$O(g(n)) = \{f(n) : \exists\, c>0,\ n_0>0 \text{ mit } 0\le\lvert f(n)\rvert\le c\,\lvert g(n)\rvert\ \ \forall n\ge n_0\}$$

In Worten: $f$ wächst höchstens so schnell wie $g$. Ab einer Stelle $n_0$ liegt $f$ immer unter einem festen Vielfachen von $g$.

Schreibweise: $f(n)=O(g(n))$ statt $f(n)\in O(g(n))$. Das „=“ ist nur in dieser Richtung zu lesen, $O(n^2)=3n$ ergibt keinen Sinn.

Beispiele mit Nachweis:

• $3n=O(n^2)$: wähle $c=3$, $n_0=1$, denn $3n\le 3n^2$ für $n\ge1$. ✔
• $n^2/2-3n = O(n^2)$: wähle $c=\tfrac12$, $n_0=6$ (ab da ist $n^2/2-3n\ge 0$ und $\le n^2/2$). ✔
• $6n^3\neq O(n^2)$: $6n^3\le cn^2 \iff n\le c/6$ gilt für kein festes $c$ für alle großen $n$. ✘

Zum Ausprobieren: Wähle $f$ und verändere $c$. Grün markiert ist der Bereich ab $n_0$, in dem die Ungleichung gilt. Bei $6n^3$ findet man für $O(n^2)$ kein $c$, das bis zum rechten Rand hält – schieb $n$ hoch und es kippt wieder.

f(n) =

c = 0.513n bis 30

■ f(n) = n²/2 − 3n  ■ c·g(n) = 0.513·n²
Im Bereich gilt |f(n)| ≤ c·g(n) für alle n ≥ n₀ = 3 (grün). Tatsächlich gilt: n²/2 − 3n = O(n²) – es gibt also passende Konstanten.

Big-Omega: untere Schranke (≥)

$$\Omega(g(n)) = \{f(n) : \exists\, c>0,\ n_0>0 \text{ mit } 0\le c\,\lvert g(n)\rvert\le\lvert f(n)\rvert\ \ \forall n\ge n_0\}$$

$f$ wächst mindestens so schnell wie $g$.

• $3n\neq\Omega(n^2)$
• $n^2/2-3n=\Omega(n^2)$: wähle $c=\tfrac14$, $n_0=12$ (dann $n^2/2-3n\ge n^2/4 \iff n\ge 12$). ✔
• $6n^3=\Omega(n^2)$

Typische Verwendung: untere Schranken für Probleme: „Jeder Algorithmus braucht mindestens $\Omega(n\log n)$“, siehe 2.3.

Big-Theta: exakte Ordnung (=)

$$\Theta(g(n)) = \{f(n) : \exists\, c_1,c_2>0,\ n_0>0 \text{ mit } 0\le c_1\lvert g(n)\rvert\le\lvert f(n)\rvert\le c_2\lvert g(n)\rvert\ \ \forall n\ge n_0\}$$

$f$ wächst genauso schnell wie $g$: eingeklemmt zwischen zwei Vielfachen von $g$. Äquivalent: $f=O(g)$ und $f=\Omega(g)$.

• $3n\neq\Theta(n^2)$
• $n^2/2-3n=\Theta(n^2)$ ✔
• $6n^3\neq\Theta(n^2)$

Small-o: echt kleiner

$$o(g(n)) = \{f(n) : \forall\, c>0\ \exists\, n_0>0 \text{ mit } 0\le\lvert f(n)\rvert < c\,\lvert g(n)\rvert\ \ \forall n\ge n_0\}$$

Unterschied zu $O$: Die Ungleichung muss für jedes noch so kleine $c$ gelten, nicht nur für ein passendes. Äquivalent:

$f(n)=o(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)} = 0.$

• $3n=o(n^2)$, denn $3n/n^2 = 3/n\to0$. ✔
• $n^2/2-3n\neq o(n^2)$, denn der Quotient geht gegen $\tfrac12\neq0$.
• $6n^3\neq o(n^2)$

Small-omega: echt größer

$$\omega(g(n)) = \{f(n) : \forall\, c>0\ \exists\, n_0>0 \text{ mit } 0\le c\,\lvert g(n)\rvert < \lvert f(n)\rvert\ \ \forall n\ge n_0\}$$

$f(n)=\omega(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)} = \infty.$

• $3n\neq\omega(n^2)$
• $n^2-3n\neq\omega(n^2)$ (Quotient $\to1$)
• $6n^3=\omega(n^2)$ (Quotient $6n\to\infty$) ✔

Überblick

Symbol	Analogie	$3n$ vs. $n^2$	$n^2/2-3n$ vs. $n^2$	$6n^3$ vs. $n^2$
$O$	$\le$	✔	✔	✘
$\Omega$	$\ge$	✘	✔	✔
$\Theta$	$=$	✘	✔	✘
$o$	$<$	✔	✘	✘
$\omega$	$>$	✘	✘	✔

Wachstumshierarchie (Ergänzung)

$$1 \;<\; \log n \;<\; \sqrt n \;<\; n \;<\; n\log n \;<\; n^2 \;<\; n^3 \;<\; 2^n \;<\; n!$$

(jeweils im Sinne von $o$). Für die konvexe Hülle sind relevant: $O(n^3)$ naiv, $O(n^2)$ Jarvis im Worst Case, $O(n\log n)$ Graham und $O(n\log h)$ Chan.

Gefühl für die Größenordnungen bei $n=10^6$ Punkten und $10^9$ Operationen pro Sekunde:

Laufzeit	Operationen	Zeit
$n\log n$	$2\cdot10^7$	0,02 s
$n^2$	$10^{12}$	ca. 17 min
$n^3$	$10^{18}$	ca. 32 Jahre