所以,在之前的一次考试中,我被要求解决以下递归方程而不使用主定理:
T(n)= 9T(n/3) + n^2
很遗憾,我在考试中无法解决它,所以我使用了主定理来解决它,只是为了知道答案(但当然,我没有得到这个问题的学分),现在我想知道如何在没有主定理的情况下解决它,因为在期末考试中,会有类似的问题。如果有人能提供逐步解决方案(并解释),那就太棒了,谢谢!
所以,在之前的一次考试中,我被要求解决以下递归方程而不使用主定理:
T(n)= 9T(n/3) + n^2
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)
,除非我犯了错误。