如何用递归树求解方程T(n) = 5T(n/5) + sqrt(n)，T(1) = 1，T(0) =0？
提问于 2017-01-25 19:43:07
关联问题
换一批
当我应用主定理时，我得到了O(n)，但当我试图用递归树来解决它时，我卡住了，找不出任何解决方案。
我试过这个：
T(n) = 5T(n/5) + sqrt(n)
T(n) = 5(5T(n/25) + sqrt(n/5)) + sqrt(n)
= 25T(n/25) + sqrt(5n) + sqrt(n)
T(n) = 5(5(5T(n/125) + sqrt(n/25)) + sqrt(n/5)) + sqrt(n)
= 125T(n/25) + sqrt(25) + sqrt(5n) + sqrt(n)
.
.
.
T(n) = sqrt(n) + sqrt(5n) + sqrt(25n) + sqrt(125n) + sqrt(625n) + sqrt(3125n) + ...我该如何解决这个GP呢？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-01-25 20:05:53
最终的和有log_5(n) + O(1)项，因为递归是最低点。最大的是sqrt(5^(log_5(n) + O(1)) n) = sqrt(O(n) n) = O(n)。其他的按几何级数递减，因此它们在big-O核算中无关紧要(或者除以1+ sqrt(1/5) + sqrt(1/5^2) + ... = Theta(1))。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41860287
复制相关文章
腾讯云开发者
