不用马斯特定理求解递归方程
Solving recurrence equation without the Master's Theorem
因此,在之前的考试中,我被要求在不使用主定理的情况下求解以下递归方程:
T(n)= 9T(n/3) + n^2
不幸的是,我在考试中想不出来,所以我用大师定理解决了它,这样我就可以知道答案了(但是,当然,我没有得到这道题的分数),并且现在我想知道没有master's theorem如何解决它因为在期末考试中会有类似的问题。
如果有人能提供一步一步的解决方案(带解释),那就太好了,谢谢!
诀窍是不断扩展,直到您看到规律。
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)
,除非我犯了一个错误。
因此,在之前的考试中,我被要求在不使用主定理的情况下求解以下递归方程:
T(n)= 9T(n/3) + n^2
不幸的是,我在考试中想不出来,所以我用大师定理解决了它,这样我就可以知道答案了(但是,当然,我没有得到这道题的分数),并且现在我想知道没有master's theorem如何解决它因为在期末考试中会有类似的问题。
如果有人能提供一步一步的解决方案(带解释),那就太好了,谢谢!
诀窍是不断扩展,直到您看到规律。
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)
,除非我犯了一个错误。