Dynamische Programmierung

Aufrufe: 180     Aktiv: 09.01.2021 um 22:14

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!

Diese Frage melden
gefragt

Student, Punkte: 64

 
Kommentar schreiben
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)

Diese Antwort melden
geantwortet

Schüler, Punkte: 385

 

Vielen Dank für deine Antwort!!!

  ─   sayuri 09.01.2021 um 22:14

Kommentar schreiben