在不使用主定理的情况下如何满足T（n）= 5T（n / 2）+ n ^ 2，T（1）= 2的渐近上限。
这是我的步骤，但是我不知道最后如何处理求和，因此无法找到此递归函数的big-O答案。
T(n) = 5T(n/2) + n^2
= 5^2 T(n/2^2) + 5(n/2)^2 + n^2
= 5^3 T(n/2^3) + 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
= ...
= 5^i T(n/2^i) + 5^i(n/2^i)^2 + ...+ 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
= 5^i T(n/2^i) + n^2 Sum of k from 0 to i, (5/4)^k
如何处理总和？谢谢。
如何处理总和？
总的来说，您在这里描述的是几何级数[wiki]。形式的总和：
n
---
\ i
/ a
---
i=0
有一个已知的解决方案：
n
--- n+1
\ i a - 1
/ a = --------
--- a - 1
i=0
所以这是您的总和：
k从0到i的总和，（5/4）^ k
等于：
4 * ((5/4)^(i+1) - 1)
我们知道这i仅限于log 2 n，这对于求解方程式是足够的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句