 dynamische Programmierung fib(n) |
|
|
| 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!?
__________________
I'm 71% Megatron!
|
|
01.02.2008 11:52 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Eigentlich brauchst du immer nur die zwei letzten Ergebnisse. Iterativ hast du es dann leicht mit O(1) Platzbedarf implementiert.
|
|
|
01.02.2008 14:46 |
|
|
|
|
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?!
__________________
I'm 71% Megatron!
|
|
|
01.02.2008 20:55 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
|
|
01.02.2008 21:19 |
|
|
|
|
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.
__________________
I'm 71% Megatron!
|
|
|
01.02.2008 21:50 |
|
|
|
