algorithm - 如何使用递归树求解方程 T(n) = 5T(n/5) + sqrt(n), T(1) = 1, T(0) = 0？

Question

当我应用主定理时，我得到 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？

Answer 1

最终总和具有 log_5(n) + O(1) 项，因为递归触底。最大的是 sqrt(5^(log_5(n) + O(1)) n) = sqrt(O(n) n) = O(n)。其他的以几何方式减少，因此它们在大 O 会计中无关紧要（或者，除以 1 + sqrt(1/5) + sqrt(1/5^2) + ... = Theta(1)） .