Der O-Kalkül, Aufwand von Algorithmen

Hat man einen Algorithmus konstruiert, so möchte man wissen wie schnell oder effizient dieser seine Aufgabe erledigt. Eine Methode, dies zu berechnen, liefert der O-Kalkül.

Hierzu betrachtet man einen Umfang von Eingabedaten (die wir mit $n$ bezeichnen), und untersuchen wie sich die Laufzeit des Algorithmus verhält wenn man $n$ stark vergrössert. Konstante Faktoren sind bei dieser Betrachtung nicht von Interesse, da Rechner um konstante Faktoren in ihrer Geschwindigkeit variieren.

Definition

Es gelten folgende Definitionen der Funktionenklassen:

\begin{align*} \mathcal{O}(g(n)) &:= \{ f(n) \;|\; \exists c > 0,\; \exists n_0 > 0: \forall n \geq n_0: 0 \leq f(n) \leq c \cdot g(n) \} \\ o(g(n)) &:= \{ f(n) \;|\; \forall c > 0: \exists n_0 > 0: \forall n \geq n_0: 0 \leq f(n) < c \cdot g(n) \} \\\;&\\ \Omega(g(n)) &:= \{f(n) \;|\; \exists c > 0,\; \exists n_0 > 0: \forall n \geq n_0: 0 \leq c \cdot g(n) \leq f(n) \} \\ \omega(g(n)) &:= \{f(n) \;|\; \forall c > 0: \exists n_0 > 0: \forall n \geq n_0: 0 \leq c \cdot g(n) < f(n) \} \\\;&\\ \Theta(g(n)) &:= \{ f(n) \;|\; \exists c_1 > 0,\; \exists c_2 > 0,\; \exists n_0 > 0: \forall n > n_0: 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \} \end{align*}

Mit Hilfe dieser Definitionen kann man leicht beschreiben, ob ein Algorithmus $f(n)$ höchstens ($\mathcal{O}(g(n)), o(g(n))$), mindestens ($\Omega(g(n)), \omega(g(n))$) oder gleich ($\Theta(g(n))$) stark wie $g(n)$ wächst.

Abschätzungen

Betrachtet man nun den Aufwand eines Algorithmus, so ist immer der Teil der Ausschlaggebende, der am stärksten wächst; Konstanten werden wie vorher schon gesagt einfach weggelassen. Für einen Algorithmus mit Aufwand $T(n) = 4n^2 + 16n$ betrachten wir also nur den $n^2$ Teil. Somit ergeben sich die folgenden, wichtigen Abschätzungen:

$\mathcal{O}(1)$ - Konstanter Aufwand
$\mathcal{O}(\log_2 n)$ - Logarithmischer Aufwand
$\mathcal{O}(n)$ - Linearer Aufwand
$\mathcal{O}(n \log_2 n)$ - Quasilinearer Aufwand
$\mathcal{O}(n^2)$ - Quadratischer Aufwand
$\mathcal{O}(n^k)$ - Polynomialer Aufwand
$\mathcal{O}(k^n)$ - Exponentieller Aufwand
$\mathcal{O}(n!)$ - Ganz ganz böse...
.
.
 Grafik über die Aufwände

Am besten ist natürlich, wenn man es schafft seinen Algorithmus so zu konstruieren, dass er einen Aufwand von $\mathcal{O}(\log n)$ hat. Ab $\mathcal{O}(n^2)$ wird es ungemütlich, und alles was darüber hinausgeht sollte tunlichst vermieden werden. Um zu illustrieren warum, ist hier eine Tabelle wieviel Daten $k$ ein Algorithmus einer bestimmten Klasse bei gleichbleibender Zeit verarbeiten kann, wenn die Rechner um den Faktor $10$ schneller werden:

$f(n)$$g(k)$
$\log_2 n$$ 1000 \cdot k $
$n$$10 \cdot k $
$n \log_2 n$$9$ bis $10\cdot k$ (für große $k$)
$n^2$$3 \cdot k$
$2^n$$k + 3$
$n!$$k$ (für $k \gg 10$)

Rekurrenzen / Rekursion

Rekurrenzen treten dann auf, wenn ein Algorithmus sich selbst aufruft. Den Aufwand solcher Algorithmen zu bestimmen kann etwas schwieriger sein. Es gibt jedoch eine "Master-Methode", wenn sich der Aufwand des Algorithmus durch folgende Form beschreiben lässt:

Es seien $a \geq 1$, $b \geq 1$ und $f(n)$ eine Funktion. Es sei folgende Rekurrenz gegeben:

\begin{gather*} T(n) = a \cdot T(\frac{n}{b}) + f(n) \end{gather*}

dann gelten diese Regeln:

\begin{gather*} T(n) \in \left\{ \begin{array}{lcl} \Theta(n^{\log_b(a)}) & \text{ falls } & f(n) \in \mathcal{O}(n^{\log_b(a) - \varepsilon}) \text{ für einige $\varepsilon > 0$} \\ \Theta(n^{\log_b(a)} \cdot \log_2 n) & \text{ falls } & f(n) \in \Theta(n^{\log_b(a)}) \\ \Theta(f(n)) & \text{ falls } & f(n) \in \Omega(n^{\log_b(a) + \varepsilon}) \\ && \text{für einige $\varepsilon > 0$ und } a \cdot f(\frac{n}{b}) \leq c \cdot f(n) \\&&\text{für $c < 1$ und genügend große $n$} \end{array} \right. \end{gather*}

Die meisten Rekurrenzen werden durch diese Methode abgedeckt. Hat man jedoch sehr abgefahrene rekursive Algorithmen, so gibt es noch den allgemeinen Beschleunigungs- und Aufteilungssatz:

Es vermag $\displaystyle T(n) = \sum_{i=1}^m T( \alpha_i \cdot n) + f(n)$ wobei $0 < \alpha_i < 1$, $m \geq 1$, $f(n) \in \Theta(n^k)$ für $k \geq 1$. Dann gilt

\begin{gather*} T(n) \in \left\{ \begin{array}{lcl} \Theta(n^k) & \text{ falls } & \sum_{i=1}^m \alpha_i^k < 1 \\ \Theta(n^k \log n) & \text{ falls } & \sum_{i=1}^m \alpha_i^k = 1 \\ \Theta(n^c) & \text{ falls } & \sum_{i=1}^m \alpha_i^k > 1 \text{ wobei $c$ bestimmt durch } \sum_{i=1}^m \alpha_i^c = 1 \end{array} \right. \end{gather*}

Es sollte klar sein, dass es immernoch Rekurrenzen geben kann, die sich nichtmal mit diesem Satz lösen lassen. Da hilft dann nurnoch raten, oder ein anderes Verfahren (Z.B. Generierende Funktionen).

Website by: Thomas Pajor, Augartenstr. 56, 76137 Karlsruhe - www.darkviper.de - with help from: flowhase