Laufzeit < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Folgern Sie, dass eien rekursive Implementierung zur Berechnung der Fibonacci-Zahlen die Laufzeit $T(n) = [mm] \Theta(\frac{1+\sqrt{5}}{2})$ [/mm] hat. |
Ich hab da jetzt mal so angefangen:
Es ist ja die genaue Schranke [mm] $\Theta$ [/mm] gefordert also muss ich die obere Schranke O und die untere [mm] $\Omega$ [/mm] untersuchen.
[mm] $\underbrace{T(n)}_{=g(n)} [/mm] = [mm] \Theta\left(\underbrace{\frac{1+\sqrt{5}}{2}}_{=f(n)}\right)$
[/mm]
1. Fall, obere Schranke O:
[mm] $\Rightarrow \lim_{n \to \infty} \frac{g(n)}{f(n)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{T(n)}{\frac{1+\sqrt{5}}{2}} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{2 \cdot T(n)}{1+\sqrt{5}} \leq [/mm] c$
$2 [mm] \cdot [/mm] T(n)$ geht gegen unendlich. Unendlich geteilt durch [mm] $1+\sqrt{5}$ [/mm] wird wohl immer noch unendlich bleiben. Somit ist wohl auch kein c zu finden, dass größer dem Unendlich sein wird. Der 1. Fall ist also schon mal falsch...
2. Fall, untere Schranke [mm] $\Omega$:
[/mm]
[mm] $\Rightarrow \lim_{n \to \infty} \frac{g(n)}{f(n)} \geq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{T(n)}{\frac{1+\sqrt{5}}{2}} \geq c\Leftrightarrow \lim_{n \to \infty} \frac{2 \cdot T(n)}{1+\sqrt{5}} \geq [/mm] c$
$2 [mm] \cdot [/mm] T(n)$ geht gegen unendlich. Unendlich geteilt durch [mm] $1+\sqrt{5}$ [/mm] wird wohl immer noch unendlich bleiben. Da hier aber nun c kleiner gleich dem Term auf der linken Seite sein soll, kann man ein c finden das passt. Aber: Da bei [mm] $\Theta$ [/mm] beide Fälle stimmen müssen, kann es nicht mehr passen, da der 1. Fall schon falsch war.
Ich hab zwar hier jetzt so eine Betrachtung gemacht, aber ich weiß nicht, ob das das geforderte war... Wie versteht ihr die Aufgabe?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:45 So 08.04.2012 | | Autor: | felixf |
Moin!
> Folgern Sie, dass eien rekursive Implementierung zur
> Berechnung der Fibonacci-Zahlen die Laufzeit [mm]T(n) = \Theta(\frac{1+\sqrt{5}}{2})[/mm]
> hat.
Ein kleiner Tipp: da sollte $T(n) = [mm] \Theta((\frac{1+\sqrt{5}}{2})^n)$ [/mm] stehen. Also mit dem "Hoch $n$". Ohne das funktioniert es nicht.
(Kennst du die ![[]](/images/popup.gif) Formel von Moire-Binet? Damit ist es recht einfach.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Mo 09.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
