解决通过替换

Question

的方法的复发时在学习的算法和参照CLRS，我碰到

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

你的第一行扩展不好，但第二行是逻辑的（仔细观察，你没有对括号做过两次同样的事情）。

这里是你如何能做到这一点：

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) 

一概而论，你可以看到，在步骤j，分解T(n-ja)会给你T(n-(j+1)a)，一个新T(a)和c(n-ja)。然后，

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) 

赋予大致

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

这是自c>0Theta(n^2)。