Dynamische Programmieralgorithmen mit Log in der Laufzeit

7

Die meisten klassischen Beispiele für dynamische Programmieralgorithmen haben Laufzeiten wie oder . Gibt es natürliche Beispiele mit einer Laufzeit von ?nn2O(nlog⁡n)

algorithms reference-request dynamic-programming Joe
quelle
Nehmen Sie einen Divide-and-Conquer-Algorithmus zum Sortieren.
Nicholas Mancuso
4
@NicholasMancuso: Teilen und Erobern ist keine dynamische Programmierung, da sich die Teilprobleme nicht überlappen.
A.Schulz
@ A.Schulz Eigentlich sind sie. Dieselbe Teilsequenz kann in mehreren Zweigen der Wiederholung auftreten (ich denke an die Mergesort-Wiederholung). Wir ignorieren dies beim Sortieren, weil wir keine weitere Beschleunigung benötigen. Die Tatsache, dass wir nur eine Partitionierung für jede Eingabe versuchen müssen, um die optimale (sortierte) Lösung zu finden, dominiert den Effekt.
Raphael

Antworten:

3

Ein natürliches Beispiel ist das Finden der am längsten ansteigenden Teilsequenz einer Folge von Zahlen. Kandidaten-Teilsequenzen können in der Eingabesequenz verknüpft werden. Dies ist eine ziemlich häufige Übung und funktioniert auch für andere Arten von Teilsequenzen. Es ist eigentlich die Übung 15.4-6 in der 3. Auflage von Cormen et al. Buch auch. Einen Algorithmus finden Sie in Abschnitt 2.2 in diesen Hinweisen .n

Juho
quelle
1

Um meinen Kommentar zu erweitern:

Beachten Sie die tatsächliche Definition von DP, während beim Sortieren keine "Tabellensuche" durchgeführt wird:

Methode zur Lösung von Problemen mit optimaler Unterstruktur.

Wir sehen, dass ein Divide-and-Conquer-Ansatz zum Sortieren dies erfüllt.

Nicholas Mancuso
quelle
1
Ich interessiere mich für eine differenziertere Definition von DP. In Ihrem Beispiel gibt es keine Unterproblemüberlappung und keine Memoisierung erforderlich.
Joe
Soweit ich weiß, gibt es keine "tatsächliche Definition von DP". Die terminale "optimale Unterkonstruktion" ist ebenfalls nicht sehr genau. In Bezug auf die Aussage Ihrer Antwort halte ich es für vernünftig, beispielsweise die Mergesort-Wiederholung als DP-Wiederholung zu bezeichnen, wenn Sie den Begriff DP auf Datentransformationsprobleme erweitern (normalerweise werden nur Optimierungs- und Entscheidungsprobleme berücksichtigt). Dies ist ein ganz besonderer Fall, da wir nur eine Partitionierung ausprobieren müssen.
Raphael
DP ist natürlich von unten nach oben, aber Divide-and-Conquer ist in Ehrfurcht (auch dies hängt nicht mit Memoisierung zusammen).
1
An alle. Ich stimme zu, dass Teilen und Erobern nicht wirklich der typischsten Form von DP entspricht. Ich hatte immer das Gefühl, dass dies aus technischen Gründen ein Sonderfall war (optimale Unterstruktur, dh Bellmans Prinzip der Optimalität). Aber angesichts von Joes Kommentar sollte ich vielleicht ein überzeugenderes Beispiel geben. ;)
Nicholas Mancuso