Dynamische Programmierung: Warum verbessert Knuth den Optimal Binary Search Tree O (n^2)?

Question

Dies ist Aufgabe 15.5-4 der Einführung in Algorithmen, 3. Ausgabe, die sich mit Knuths Verbesserung des DP-Ansatzes zum Optimal Binary Search Tree beschäftigt.

Der DP-Algorithmus von Optimal Binary Search Tree ist:

OPTIMAL_BST(p, q, n) 
let e[1..n+1, 0..n], w[1..n+1, 0..n], and root[1..n, 1..n] be new tables 
for i = 1 to n+1 
    e[i, i - 1] = q[i - 1]; 
    w[i, i - 1] = q[i - 1]; 
for l = 1 to n 
    for i = 1 to n - l + 1 
     j = i + l - 1 
     e[i, j] = INFINITY 
     w[i, j] = w[i, j - 1] + p[j] + q[j] 
     for r = i to j 
      t = e[i, r - 1] + e[r + 1, j] + w[i, j] 
      if t < e[i, j] 
      e[i, j] = t 
      root[i, j] = r 
return e and root 

Die Komplexität ist O (n). Knuth hatte beobachtet, dass root[i, j - 1] <= root[i, j] <= root[i + 1, j], so Aufgabe 15.5-4 fragt, um einen O (n) Algorithmus zu implementieren, indem einige Änderungen an dem ursprünglichen Algorithmus vorgenommen werden.

Nun nach einiger Mühe habe ich dies herausgefunden: in der innersten Schleife, ersetzen Sie die Zeile

for r = i to j 

mit

for r = r[i, j - 1] to r[i + 1, j] 

Dies wird durch diesen Link bewiesen worden: Optimal binary search trees

Allerdings bin ich mir nicht sicher, ob das wirklich O ist (n): da während jeder innersten Schleife der Abstand von r [i, j - 1] zu r [i + 1, j] ist nicht konstant, ich vermute, es ist immer noch O (n).

Also meine Frage ist: Können Sie mir bitte erklären, warum die Verbesserung der DP-Algorithmus ergibt O (n) Komplexität?

PS: Vielleicht habe ich zuerst Knuths Papier gelesen, aber ich habe wirklich im Internet gesucht, aber keinen freien Zugang zum Papier gefunden.

Answer 1

Sie haben Recht, dass der Abstand von r[i, j - 1] zu r[i + 1, j] im ungünstigsten Fall nicht konstant ist, aber im Durchschnitt konstant ist, was ausreicht, um eine quadratische Laufzeit zu implizieren. Die Gesamtzahl der Iterationen für l ist

S = sum_{i = 1}^{n - l + 1} (r[i + 1, j] + 1 - r[i, j - 1]), j = i + l - 1 
    = sum_{i = 1}^{n - l + 1} (r[i + 1, i + l - 1] + 1 - r[i, i + l - 2]) 
    = r[n - l + 2, n] + n - l + 1 - r[1, l - 1] 

daher ist die durchschnittliche S/(n - l + 1), die eine Konstante ist

durch die teleskopier Summe vereinfacht.

Answer 2

Sie können die genaue Laufzeitanalyse mit einer Google-Suche finden oder einfach beginnen, Ihre eigene Analyse w.r.t für Schleifen zu schreiben. Aber beachte, dass in allen von ihnen Summe Summe berechnet wird durch teleskopische Summe, ich meine vielleicht eine von ihnen ist groß, aber in jeder Iteration für die erste Schleife dauert O (n), und nimmt völlig O (n).