当我应用主定理时，我得到 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)。其他的呈几何级数减少，因此它们在大 O 会计中无关紧要(或者，除以 1 + sqrt(1/5) + sqrt(1/5^2) + ... = Theta(1)) .
关于algorithm - 如何使用递归树求解方程 T(n) = 5T(n/5) + sqrt(n), T(1) = 1, T(0) = 0？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41860287/