T(n) = 9T(n/2)+n^3 使用主定理求解递归方程

Question

我按照这个定理来解决它：

我对这道题的解法：9T(n/2)+n^3 是theta(n^log base 2 (9))，对吗？如果不是，为什么？

提前致谢！

Answer 1

制作

n = 2^m

并替换我们有

T[2^m] = 9 T[2^(m-1)]+2^(3m)

可以改写为

R[m] = 9 R[m-1] + 2^(3m)

这个线性递归可以用

R[m] = Rh[m] + Rp[m]

来解决

Rh[m] - 9 Rh[m-1] = 0

和

Rp[m] - 9 Rp[m-1] = 2^(3m)

和

Rh[m] = c0 9^m

。现在考虑

Rp[m] = c0[m]9^m

并代入我们得到的完全递归

c0[m]9^m-9c0[m-1]9^(m-1) = 2^(3m)

或

c0[m] -c0[m-1] = (8/9)^m

因此

c0[m] = ((8/9)^(m+1) - 1)/((8/9) - 1)

所以

Rp[m] = ((8/9)^(m+1) - 1)/((8/9) - 1)9^m

因此

R[m] = (c0 + ((8/9)^(m+1) - 1)/((8/9) - 1)9^m

最后获得

T[n]

所需的后退步骤留给读者。