如何使用递归树求解方程 T(n) = 5T(n/5) + sqrt(n), T(1) = 1, T(0) = 0？
How to solve equation T(n) = 5T(n/5) + sqrt(n), T(1) = 1, T(0) = 0 using recursion tree?
当我应用主定理时，我得到 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 )).
当我应用主定理时，我得到 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 )).