| Die letzten 5 Beiträge |
| 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. |
| Tobias |
Nein, im Gegenteil: Dynamische Programmierung heißt Rekursionen vermeiden.
http://de.wikipedia.org/wiki/Dynamische_Programmierung |
| 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?! |
| Tobias |
Eigentlich brauchst du immer nur die zwei letzten Ergebnisse. Iterativ hast du es dann leicht mit O(1) Platzbedarf implementiert. |
| 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!? |
|
|
