当我应用主定理时，我得到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？
由于递归触底，所以最终的总和具有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）） 。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句