Programmazione dinamica: Perché il miglioramento di Knuth nell'albero di ricerca binaria ottimale O (n^2)?

Question

Questo è l'esercizio 15.5-4 di Introduction to Algorithms, 3a edizione, che tratta del miglioramento di Knuth rispetto all'approccio DP a Optimal Binary Search Tree.

L'algoritmo DP di Optimal Binary Search Tree è:

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 

La complessità è O (n). Knuth aveva osservato che root[i, j - 1] <= root[i, j] <= root[i + 1, j], quindi l'esercizio 15.5-4 richiede di implementare un algoritmo O (n) apportando alcune modifiche all'algoritmo originale.

Beh, dopo qualche sforzo ho capito questo: nel ciclo più interno, sostituire la linea

for r = i to j 

con

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

Questo è stato dimostrato da questo link: Optimal binary search trees

Tuttavia, non sono sicuro che sia davvero O (n): poiché durante ogni ciclo più interno, la distanza da r [i, j - 1] a r [i + 1, j] non è costante, ho il sospetto che sia ancora O (n).

Quindi la mia domanda è: può spiegarmi perché il miglioramento dell'algoritmo DP produce O (n) complessità?

PS: Forse avrei potuto leggere prima il lavoro di Knuth, ma in realtà ho cercato nel web ma non ho trovato alcun accesso gratuito al giornale.

Answer 1

Hai ragione che la distanza da r[i, j - 1] a r[i + 1, j] non è costante nel peggiore dei casi, ma è costante in media, il che è sufficiente a implicare un tempo di esecuzione quadratico. Il numero totale di iterazioni per l è

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] 

quindi la media è S/(n - l + 1), che è una costante

semplificando la somma telescopico.

Answer 2

È possibile trovare l'esatta analisi del tempo di esecuzione con una ricerca su google o semplicemente iniziare a scrivere la propria analisi w.r.t per i loop. Ma si noti che in tutti loro la somma totale è calcolata dalla somma telescopica, voglio dire che uno di essi è grande ma in ogni iterazione per il primo ciclo prende O (n) e prende totalmente O (n).