Analyse eines rekursiven Programms

Beispiel:

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

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

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:

$$\alpha^{n} = \alpha^{n-1} + \alpha^{n-2} + 1$$

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$.