在没有Master's定理的情况下求解递推方程

Question

因此,在之前的考试中,我被要求在不使用主定理的情况下求解以下递推方程:

T(n)= 9T(n/3) + n^2

不幸的是,我无法在考试中弄明白,所以我使用硕士定理解决了它,所以我可以知道答案(当然,我对这个问题没有任何赞誉),现在我想知道如何在没有主人定理的情况下解决它,因为在期末考试中,会有类似的问题.

如果有人可以提供一步一步的解决方案(有解释),那就太棒了,谢谢!

Answer 1

诀窍是继续扩展,直到你看到模式.

T(n) 
= 9 T(n/3) + n^2 
= 9(9T(n/3^2) + n^2/3^2) + n^2 
= 9^2 T(n/3^2) + 2n^2
= 9^2 (9 T(n/3^3) + n^2/3^4) + 2n^2
= 9^3 T(n/3^3) + 3n^2
= ...
= 9^k T(n/3^k) + kn^2

这一直持续到k为3 ^ k = n.

假设T(1)=1,你得到 T(n) = n^2 +kn^2 = n^2 + log_3(n) n^2.

所以看起来T(n) = O(n^2 logn),除非我犯了错误.