Memoization-oder Tab-Ansatz für die Dynamische Programmierung

Gibt es viele Probleme, die gelöst werden können mit Hilfe der Dynamischen Programmierung z.B. Längsten steigenden Teilfolge. Dieses problem kann gelöst werden, indem 2 Ansätze

  1. Memoization (Top-Down) - Mit Rekursion zu lösen, das sub-problem und speichern das Ergebnis in einigen hash-Tabelle.
  2. Auswertung (Bottom-Up) - Einsatz von Iterativen Ansatz zur Lösung des Problems durch die Lösung der kleinere sub-Probleme zuerst und dann verwenden Sie es während der Ausführung ein größeres problem.

Meine Frage ist was ist besser-Ansatz in Bezug auf Zeit und Raum Komplexität?

  • Die zweite option ist nicht wirklich dynamisch-Programmierung, es ist mehr verringern und zu erobern. Es ist abhängig von der problem-Größe und was das problem versucht zu lösen in der Analyse.
  • Abhängig von problem natürlich.
  • Wenn es eine " cut-and-getrocknet, allgemeingültige Antwort, das Leben wäre einfacher und in allen Lehrbüchern würde nur lehren Sie die "richtige" Art und Weise. Aber gibt es nicht eine allgemeingültige Antwort. Auch das Wort " memoization.' Kein 'R'.
  • warum heißt es memoization? das Auswendiglernen scheint die apt Wort wie merken wir uns das Ergebnis der kleinere sub-Probleme.
  • en.wikipedia.org/wiki/Memoization#Etymology
InformationsquelleAutor Mady | 2012-08-20
  1. 33

    Kurze Antwort: es hängt von dem problem!

    Memoization erfordert in der Regel mehr code und ist nicht ganz so einfach, aber hat rechnerische Vorteile in einige Probleme, vor allem diejenigen, die Sie tun nicht brauchen, um zu berechnen, werden alle Werte für die gesamte matrix zu erreichen, ist die Antwort.

    Auswertung ist einfacher, kann aber berechnen überflüssigen Werte. Wenn Sie brauchen, um zu berechnen, werden alle Werte, diese Methode ist für gewöhnlich schneller, aber wegen der geringeren overhead.

    InformationsquelleAutor behnam
  2. 1

    Asymptotisch einem dynamischen Programmierung Implementierung von top-down ist das gleiche wie der Gang von unten nach oben, vorausgesetzt, Sie sind mit der gleichen Wiederholung Bezug. Jedoch, bottom-up ist in der Regel effizienter, weil der Aufwand der Rekursion die in memoization.

    InformationsquelleAutor weeb
  3. -4

    Wenn das problem overlapping sub-problems - Eigenschaft verwenden Sie dann Memoization, sonst kommt es auf das problem

    • Für überlappende sub-Probleme, die wir verwenden können, - Auswertung zu.
    • Ja, Sie können, aber memoization entfernt redundante Berechnungen
    InformationsquelleAutor arunmoezhi
Schreibe einen Kommentar