Rekursive Fibonacci-Implementierung: Exponentielle Laufzeit

Hallo,

in einem englischen Buch über Algorithmen / Datenstrukturen habe ich mal einen Beweis dafür gelesen, dass eine rekursive Fibonacci-Implementierung exponentielles Laufzeitwachstum hat. Dazu wurde eine Abschätzung verwendet, die als Hilfslemma zuvor induktiv bewiesen wurde.

Leider kann ich mich an das Buch nicht erinnern, im Internet habe ich den Beweis nicht mehr gefunden, nun würde ich mir den spaßhalber gern mal wieder reinjodeln.

Hat jemand den Beweis zufällig zur Hand, oder einen Link?

Erklärungen brauch ich nicht, ich habe das Prinzip schon verstanden. Ich will einfach nochmal den Beweis lesen.

Gruß
Roflnacci

SeppJ

roflnacci schrieb:

dass eine rekursive Fibonacci-Implementierung exponentielles Laufzeitwachstum hat.

Unmöglich. Ich kann dir rekursive Fibonacci-Implementierungen hinschreiben, die in log(N) laufen (indem ich eine unnötige Rekursion in den log(N)-Algo einbaue). Man kann natürlich beweisen, dass

int Fib(int n)
{
    if (n <= 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

exponentielles Laufzeitverhalten hat, sofern man es nicht schon sofort auf den ersten Blick sieht. Hier:
Google: recursive fibonacci complexityDer zweite Link ist sogar zu einem Teil aus deinem/einem Buch.

Hi SeppJ,

danke für deine Antwort. Ja, ich beziehe mich auf die "naive" Fibonacci-Implementierung.

Der zweite Link hat mir geholfen, hab die stackoverflow-Sachen iwie ignoriert. Ich glaube aber, dass der Beweis damals ein anderer war. Es ging eine Abschätzung vorraus, die induktiv bewiesen wurde. Da ich es gedanklich nicht mehr im Ansatz zusammenbekomme, was da passierte, interessiert mich ja das nochmalige Einsehen des Beweises so sehr

Im Notfall geh ich halt in die Uni-Bibliothek und schau nochmal nach dem Buch...

nachtfeuer

Vielleicht hilft statt einem Buchtext ja auch einfach das direkte selber machen/ausbrobieren/angucken, learning by doing:

Auf der einen Seite

mov rcx,Zahl
schleife
   add rax,rbx ;rax = 0 rbx = 1
   add rbx,rax
   loop schleife

anschauen und nachrechnen

oder eben den Haskell Gassenhauer (mit coolem Pattern-Matching)

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

wie er auf der Haskellwikiseite http://www.haskell.org/haskellwiki/The_Fibonacci_sequence steht, von Hand nachzeichnen, und Rechenschritte zählen.
(Und man könnte auch die Zeit messen, wie lange man selber dran sitzt, bei sagen wir mal Zahl/n=5 und Zahl/n=12 und Zahl/n=32 oder/und man misst zusätzlich noch den inneren Widerstand, der den Unterschied ausmacht )

Was soll ich dazu sagen?
Ich habe oben ja explizit gesagt, es ginge mir nicht ums Verständnis (die Zeit, wo ich das gelernt habe, ist schon eine Weile her und verstanden habe ich es auch), ich wollte einfach nochmal diesen Beweis sehen.
Es geht mir also schlicht um die mathematische Methodik des Beweisens, nicht um den Sachverhalt an sich.

Hast auch du das nun verstanden?

nachtfeuer

roflnacci schrieb:

Hast auch du das nun verstanden?

Könnte ich jetzt auch fragen: Hätte ich "Learnig by Doing" besser auf Deutsch formulieren sollen?

Naja, "praktische Erinnerungshilfe" wäre dann vielleicht verständlicher (oder treffender) ?

nachtfeuer schrieb:

Könnte ich jetzt auch fragen: Hätte ich "Learnig by Doing" besser auf Deutsch formulieren sollen?

Nein Du hättest Dir Deinen Beitrag einfach sparen können. Irgendein Assembler-Gefrickel und Haskell-Code haben rein garnichts mit der Fragestellung zu tun.

Danke, 2358