big-o - 在没有大师定理的情况下求解递归方程

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)，除非我犯了一个错误。