Dynamische Programmierung

Aufrufe: 42     Aktiv: 1 Woche her

0

Hallo zusammen

Es gibt zwei Ansätze Bottom Up Approach und Top Down Approach. Wann genau braucht man Dynamische Programmierung, wenn man Werte zwischenspeichern möchte? Wie z.B. Fibonacci Berechnung, damit dieselbe Berechnung nicht nochmals berechnet wird?

Vielen Dank!

gefragt 1 Woche, 1 Tag her
sayuri
Student, Punkte: 36

 
Kommentar schreiben Diese Frage melden
1 Antwort
1

Ja genau, Dynamische Programmierung brauchst du immer dann, wenn du Dinge, die du zuvor schon berechnet hast, nicht noch mal berechnen musst, sondern in einer Datenstruktur speicherst und dir dann den Wert einfach dort rausholst. Wenn du dir Fibonacci anschaust, dann merkst du schnell, dass du fast jeden rekursiven Aufruf, doppelt oder noch öfter machst ... mithilfe von Dynamischer Programmierung kannst du einen berechneten Wert, z.B. in einer Hashtable speichern und wenn du ihn nochmal benötigst, kannst du ihn in der Hashtable auslesen ... Dadurch hast du eine Laufzeitkomplexität von O(n) anstatt O(2^n)

geantwortet 1 Woche her
daniel.kuenkel
Schüler, Punkte: 190
 

Vielen Dank für deine Antwort!!!

  ─   sayuri 1 Woche her
Kommentar schreiben Diese Antwort melden