Rekurrenz durch Substitution < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:19 Fr 27.10.2006 | | Autor: | Lili06 |
| Aufgabe | | Lösen Sie die Rekurrenz f(n) = [mm] f(\sqrt(n)+1 [/mm] durch Substitution. |
Also, ich habe n durch [mm] 2^t [/mm] , t [mm] \in \IN [/mm] substituiert:
[mm] f(2^t) [/mm] = [mm] f(\sqrt{2^t}) [/mm] - 1 = [mm] \dots [/mm]
[mm] \gdw f(2^t) [/mm] = [mm] f(2^{t * \frac{1}{2^i}})-i [/mm] (I.)
Nun benötige ich eine Anfangsbedingung. In der Frage steht nichts.. also gehe ich von f(2) = 1 aus.
Also muss ich [mm] 2^{t * \frac{1}{2^i}} [/mm] = 2 setzen und nach i auflösen.
[mm] \gdw [/mm] i = [mm] log_2 [/mm] t
Dies setze ich in I. ein und erhalte
[mm] f(2^t) [/mm] = 2 - [mm] log_2 [/mm] t
Nun müsste ich doch die Substitution rückgängig machen... also
f(n) = 2 - [mm] log_2 [/mm] t
Was sagt sagt mir das Ergebnis? Habe ich die Aufgabe überhaupt richtig verstanden bzw. bin ich richtig vorgegangen?
Wenn ich einen Algorithmus habe und es rekursiv aufrufe, erhalte ich eine Rekurrenzgleichung, die ich auflösen kann... was suche ich denn? Wahrscheinlich die Laufzeit und ich will eine Gleichung haben mit der ich nach i-Schritten den Aufwand berechnen kann?
Würd mich auf Hilfe sehr freuen
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 So 29.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
