Aufwandsabschätzung Fibonacci < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:39 Di 30.11.2010 | | Autor: | iMod109 |
| Aufgabe | Bestimme die Laufzeit der folgenden Rekurrenzgleichung:
T(n)=T(n-1)+T(n-2) mit T(1) = T(2)= 1 |
Hallo zusammen,
ich habe einen naiven rekursiven Algorithmus, der die Fibonaccizahlen rekursiv berechnet (ist sehr ineffizient, aber so gewollt).
Jetzt möchte ich die Laufzeit abschätzen. Das Master-Theorem ist hier nicht anwendbar. Weitere Möglichkeit wäre abschätzen und per Induktion beweisen... Dabei wird die Lösung aber geraten und das widerstrebt mir etwas.
Gibt es eine Möglichkeit aus der Rekurrenzgleichung auf die Laufzeit zu kommen( [mm] O(2^{n}))?
[/mm]
Dies ist eine sehr grobe Abschätzung aber für meine Zwecke (Einsatz im Schulunterricht) sinnvoll.
Ich habe die Abschätzung getroffen, dass T(n)=2T(n-1) ist. Dann wird aus einem Ausdruck T(n) zwei nämlich 2*T(n-1). Dieser Ausdruck wird zu vier Ausdrücken etc. bis man nach n-(n-2) Schritten terminiert. Daraus habe ich dann grob [mm] 2^{n} [/mm] abgeleitet.
So ganz glücklich bin ich damit nicht, deshalb meine Frage. Danke für eure Hilfe.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:58 Mi 01.12.2010 | | Autor: | felixf |
Moin!
> Bestimme die Laufzeit der folgenden Rekurrenzgleichung:
> T(n)=T(n-1)+T(n-2) mit T(1) = T(2)= 1
> Hallo zusammen,
> ich habe einen naiven rekursiven Algorithmus, der die
> Fibonaccizahlen rekursiv berechnet (ist sehr ineffizient,
> aber so gewollt).
>
> Jetzt möchte ich die Laufzeit abschätzen. Das
> Master-Theorem ist hier nicht anwendbar. Weitere
> Möglichkeit wäre abschätzen und per Induktion
> beweisen... Dabei wird die Lösung aber geraten und das
> widerstrebt mir etwas.
>
> Gibt es eine Möglichkeit aus der Rekurrenzgleichung auf
> die Laufzeit zu kommen( [mm]O(2^{n}))?[/mm]
Also streng genommen ist die Laufzeit [mm] $\Theta(\phi^n)$, [/mm] wobei [mm] $\phi [/mm] = [mm] \tfrac{1 + \sqrt{5}}{2} \approx [/mm] 1.618$ ist. Da [mm] $2^n \not\in \Theta(\phi^n)$ [/mm] ist, ist [mm] $O(2^n)$ [/mm] also zu grob abgeschaetzt 
(Wobei beides in [mm] $e^{O(1) n}$ [/mm] liegt.)
> Dies ist eine sehr grobe Abschätzung aber für meine
> Zwecke (Einsatz im Schulunterricht) sinnvoll.
> Ich habe die Abschätzung getroffen, dass T(n)=2T(n-1)
> ist.
Du meinst $T(n) [mm] \le [/mm] 2 T(n - 1)$, oder?
> Dann wird aus einem Ausdruck T(n) zwei nämlich
> 2*T(n-1). Dieser Ausdruck wird zu vier Ausdrücken etc. bis
> man nach n-(n-2) Schritten terminiert. Daraus habe ich dann
> grob [mm]2^{n}[/mm] abgeleitet.
Ja, das geht.
> So ganz glücklich bin ich damit nicht, deshalb meine
> Frage.
Eine Moeglichkeit ist, erst die Rekurrenzgleichung zu loesen. Dazu schaut man sich das char. Polynom [mm] $x^2 [/mm] - x - 1$ dazu an (welches von der Gleichung [mm] $x_{n+2} [/mm] - [mm] x_{n+1} [/mm] - [mm] x_n [/mm] = 0$ kommt), bestimmt die Nullstellen, die hier [mm] $\phi [/mm] = [mm] \frac{1 + \sqrt{5}}{2}$ [/mm] und [mm] $\psi [/mm] = [mm] \frac{1 - \sqrt{5}}{2}$ [/mm] sind, und kann dann $A, B [mm] \in \IR$ [/mm] bestimmen mit [mm] $a_n [/mm] = A [mm] \phi^n [/mm] + B [mm] \psi^n$ [/mm] fuer alle $n$.
Da [mm] $\psi \le \phi$ [/mm] sieht man sofort, dass [mm] $a_n \le [/mm] 2 [mm] \max\{ A, B \} \phi^n$ [/mm] ist, und mit [mm] $\phi \le [/mm] 2$ bekommt man somit [mm] $a_n \in O(2^n)$.
[/mm]
Jetzt muss man aber begruenden, warum man die Rekurrenzgleichung so loesen darf, was das ganze nur bedingt einfacher macht Dafuer wird jedoch alles brav explizit abgeschaetzt und nichts "geraten" 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Fr 31.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
