résoudre le recurrance par la méthode de substitution

Question

Tout en apprenant les algorithmes et en se référant à CLRS, je suis tombé sur un problème

T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0 
it is Big-theta(n^2), can be easily proved by recursion tree method 

Je peux le résoudre par la méthode de l'arbre de récursivité. En discutant avec des amis dans mon laboratoire, un ami a déclaré de nulle part que ce problème ne peut jamais être résolu par la méthode de substitution.

J'ai essayé de le résoudre moi-même, mais je ne trouve aucun motif en tant que tel.

De plus, mon expansion dans la première étape me semble un peu mal à:

T(n) = T(n-2a + T(a) + c(n-1)) + T(a) + cn 
T(n) = T(n-3a + 2T(a) + c(n-1)(n-2)) + T(a) + cn 

Et cela semble aller nulle part ..

Pouvez-vous le résoudre par la méthode de substitution? Quelle est votre 'deviner'?

Answer 1

Votre première ligne d'expansion n'est pas bonne, mais la seconde est logique (regardez de près, vous n'avez pas fait deux fois la même chose en ce qui concerne les crochets).

Voici comment vous pouvez le faire:

T(n) = T(n-a) + T(a) + cn 
T(n) = T(n-2a) + T(a) + c(n-a) + (T(a) + cn) 
    = T(n-2a) + 2T(a) + c(2n-a) 
    = T(n-3a) + T(a) + c(n-2a) + (2T(a) + c(2n-a)) 
    = T(n-3a) + 3T(a) + c(3n - 3a) 
... 
    = T(n-ka) + kT(a) + ck(n - (k-1)a/2) // The last part come from n+(n-a)+...+(n-(k-1)a) = k(n - (k-1)a/2) 

Généraliser, vous pouvez voir que, à l'étape j, décomposition T(n-ja) vous donnera T(n-(j+1)a), une nouvelle T(a), et un c(n-ja). Ensuite,

Sum(c(n-ja), j=0..k-1)=c*(k*n - a*Sum(j), j=0..k-1)) 
         = c(kn-a*(k-1)k/2) 

Ce qui vous donne le résultat.

Prenez k=n/a, vous obtenez:

T(n) = T(0) + nT(a)/a + c(n/a)(n-(n/a-1)a/2) 

qui donne à peu près

T(n) ~ nT(a)/a + c n^2 /(2a) 

qui est Theta(n^2) depuis c>0.