アルゴリズムを学習し、CLRSを参照しながら置換

Question

の方法によりrecurranceを解決、私は再帰ツリーの方法でそれを解決することができます

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 

問題に出くわしました。

友人は私の研究室で友人と話し合っているが、この問題は決して代替方法では解決できないと宣言した。

私はそれを自分で解決しようとしましたが、そのようなパターンは見つかりませんでした。

また、私の最初のステップで拡大することは私には多少間違っているようだ：

あなたは、置換の方法でそれを解決することができます。..

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 

そして、これはどこにも行かないしているようですか？あなたの「推測」は何ですか？

Answer 1

あなたの最初の展開は良くありませんが、2番目の展開は論理的です（括弧で2回は同じことをしていません）。ここで

は、あなたがそれを行うことができる方法である：

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) 

は、あなたがあなたのT(n-(j+1)a)、新しいT(a) 1、およびc(n-ja)を与えるT(n-ja)を分解し、ステップjで、それを見ることができる、一般化するため。次に、

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) 

結果が得られます。

k=n/aを取り、あなたが得る：

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

c>0以来Theta(n^2)でおよそ

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

を与えます。