prev up next

Previous: Analyse von while-Schleifen Up: O-Notation Next: Korrektheit und Terminierung

Analyse eines rekursiven Programms

Beispiel:

Die Laufzeit von $fib(n)$ beträgt:

\begin{displaymath}
f(n) = \left\{
\begin{array}{ll}
1,&\mbox{ falls } n \leq 1\\
f(n-1)+f(n-2)+1& \mbox{ sonst }
\end{array}\right.
\end{displaymath}

Offenbar gilt: $f {\in} O( {\alpha} ^ {n})$ für ein $ \alpha < 2$ (denn $f(n)=f(n-1)+f(n-1)$ würde zu $O(2^{n})$ führen).

Gesucht ist also ein $\alpha$, so dass für große $ n $ gilt:

\begin{displaymath}
\alpha^{n} = \alpha^{n-1} + \alpha^{n-2} + 1\end{displaymath}

Teile durch $\alpha^{n-2}$:

$\Rightarrow$
$ \alpha^{2} = \alpha + 1 + \frac {1} {\alpha^{n-2}}$. Für $n \rightarrow \infty $ und $ \alpha > 1$ geht $ \frac {1} { \alpha^{n-2}} \rightarrow 0$.
$\Rightarrow$
$ \alpha^{2} = \alpha + 1 \Rightarrow \alpha = \frac {1} {2} +
\sqrt {\frac {1}{4} + 1} = 1.61803 $ (gemäß Formel $ - \frac{p} {2} \pm \sqrt{ \frac {p^{2}} {4}-q}$ )
$\Rightarrow$
Das rekursive Fibonacci-Programm hat die Laufzeit $O(1.62^{n})$, wobei $ n $ der Wert des Inputs ist, nicht seine Länge!
für $n=20$ ist $1.62^{n}$ $\approx 15.000$
  $2^{n}$ $\approx 1.000.000$.


prev up next
Previous: Analyse von while-Schleifen Up: O-Notation Next: Korrektheit und Terminierung