dynamische Programmierung fib(n)

01.02.2008, 11:52	Auf diesen Beitrag antworten »
JROppenheimer	dynamische Programmierung fib(n) So, jetzt wo D&C erfolgreich abgehakt ist, quäle ich mich mit dynamischer Programmierung. Gerade jetzt mit der FibonacciFolge. Die rekursive Implementierung (simpelste) hat eine Laufzeit, die ähnlich wie die FibinacciFolge selbst steigt, sowas wie T(n) in O(1/sqrt(5) * (1,681...)^n) Wenn man aber die ganzen doppelten Rekursionsaufrufe zwischenspeichert, kann man lineare Laufzeit erreichen O(n). Das hab ich schon verstanden, und das bekomm ich denke ich auch recht schnell hin. Ich soll jedoch in der Aufgabe mit Platzbedarf O(1) arbeiten. DAs heisst doch konstant, und nicht abhängig von n. Wenn ich aber fib(n) implementieren will muss ich doch n-1 rekursive Zwischenschritte speichern, oder? Wie kann ich dann bei konstantem PLatz bleiben!?


01.02.2008, 14:46	Auf diesen Beitrag antworten »
Tobias	Eigentlich brauchst du immer nur die zwei letzten Ergebnisse. Iterativ hast du es dann leicht mit O(1) Platzbedarf implementiert.
01.02.2008, 20:55	Auf diesen Beitrag antworten »
JROppenheimer	ja daran dachte ich auch. aber irgendwie ist es doch witzlos, wenn ich um da zu lösen aus der rekursion ne iteration mache. heisst dynamisch programmierung net IMMER rekursiv?!
01.02.2008, 21:19	Auf diesen Beitrag antworten »
Tobias	Nein, im Gegenteil: Dynamische Programmierung heißt Rekursionen vermeiden. http://de.wikipedia.org/wiki/Dynamische_Programmierung
Anzeige

01.02.2008, 21:50	Auf diesen Beitrag antworten »
JROppenheimer	Da steht zwar, dass kostspielige rekursionen vermieden werden sollen, durch memoisation, aber Fib kann dynamisch immernoch rekursiv gelöst werden, nur ist das dann mit dem Platzbedarf bissie kritisch bei O(1), oder? Mit Memoisation ist die Laufzeit linear, aber halt auch linearer Platzbedarf, wenn ich das so überblicke.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »