用代入法解决递归

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

这似乎无处可去..

你能用代换的方法解决吗？你的 'guess' 是多少？

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)

这是 Theta(n^2) 因为 c>0.

用代入法解决递归

solving the recurrance by the method of substitution

algorithm

computer-science

proof

clrs