Wann kann ich mit dynamischer Programmierung die zeitliche Komplexität meines rekursiven Algorithmus reduzieren?

Dynamisches Programmieren kann die Zeit reduzieren, die zum Ausführen eines rekursiven Algorithmus erforderlich ist. Ich weiß, dass dynamisches Programmieren die zeitliche Komplexität von Algorithmen reduzieren kann. Sind die allgemeinen Bedingungen so, dass bei Erfüllung durch einen rekursiven Algorithmus die Verwendung einer dynamischen Programmierung die zeitliche Komplexität des Algorithmus verringert? Wann sollte ich dynamische Programmierung verwenden?

Dynamische Programmierung ist nützlich, wenn Ihr rekursiver Algorithmus häufig die gleichen Situationen (Eingabeparameter) erreicht. Es gibt eine allgemeine Transformation von rekursiven Algorithmen zu dynamischer Programmierung, die als Merken bezeichnet wird. In dieser Tabelle werden alle Ergebnisse gespeichert, die jemals durch Ihre rekursive Prozedur berechnet wurden. Wenn die rekursive Prozedur für eine Reihe von Eingaben aufgerufen wird, die bereits verwendet wurden, werden die Ergebnisse nur aus der Tabelle abgerufen. Dies reduziert rekursives Fibonacci auf iteratives Fibonacci.

Die dynamische Programmierung kann noch intelligenter sein und spezifischere Optimierungen anwenden. Beispielsweise ist es manchmal nicht erforderlich, die gesamte Tabelle zu einem bestimmten Zeitpunkt im Speicher zu speichern.

Wenn Sie nur versuchen, Ihren rekursiven Algorithmus zu beschleunigen, ist die Speicherung möglicherweise ausreichend. Dies ist die Technik zum Speichern der Ergebnisse von Funktionsaufrufen, sodass zukünftige Aufrufe mit denselben Parametern das Ergebnis einfach wiederverwenden können. Dies gilt nur für Ihre Funktion

• hat keine Nebenwirkungen und
• hängt nur von seinen Parametern ab (dh nicht von einem Zustand).

Sie sparen Zeit, wenn (und nur wenn) die Funktion immer wieder mit denselben Parametern aufgerufen wird. Beliebte Beispiele sind die rekursive Definition der Fibonacci-Zahlen

$\qquad \begin{align} f(0) &= 0 \\ f(1) &= 1 \\ f(n+2) &= f(n+1) + f(n) \qquad ,\ n \geq 0 \end{align}$

$f$$f(n)$$f(n+1)$

Beachten Sie, dass die Speicherung für Algorithmen wie Merge-Sort nahezu unbrauchbar ist: In der Regel sind nur wenige (wenn überhaupt) Teillisten identisch, und Gleichheitsprüfungen sind teuer (das Sortieren ist nur geringfügig teurer!).

In praktischen Implementierungen ist es für die Leistung von großer Bedeutung, wie Sie Ergebnisse speichern. Die Verwendung von Hash-Tabellen ist zwar naheliegend, kann jedoch die Lokalität beeinträchtigen. Wenn es sich bei Ihren Parametern um nicht negative Ganzzahlen handelt, sind Arrays eine natürliche Wahl, können jedoch einen hohen Speicheraufwand verursachen, wenn Sie nur einige Einträge verwenden. Memoisation ist daher ein Kompromiss zwischen Wirkung und Kosten; Ob es sich auszahlt, hängt von Ihrem speziellen Szenario ab.

Dynamisches Programmieren ist eine ganz andere Sache. Es gilt für Probleme mit der Eigenschaft, dass

• es kann in Teilprobleme unterteilt werden (wahrscheinlich auf mehrere Arten),
• diese Teilprobleme können unabhängig voneinander gelöst werden,
• (optimale) Lösungen dieser Teilprobleme können zu (optimalen) Lösungen des ursprünglichen Problems und kombiniert werden
• Unterprobleme haben die gleiche Eigenschaft (oder sind trivial).

Dies wird normalerweise (implizit) impliziert, wenn Leute Bellmans Optimalitätsprinzip aufrufen .

Dies beschreibt nur eine Klasse von Problemen , die durch eine bestimmte Art von Rekursion ausgedrückt werden können. Die Auswertung dieser ist (oft) effizient, da die Memoisierung sehr effektiv eingesetzt werden kann (siehe oben). In der Regel treten kleinere Teilprobleme als Teil vieler größerer Probleme auf. Beliebte Beispiele sind die Bearbeitungsentfernung und der Bellman-Ford-Algorithmus .