用替换法求解递推方程

Question

我试图通过绘制一棵恢复树并将其求解为替换方法来求解T（n）=sqrt（n）*T（sqrt（n））sqrt（n）。但是我很难理解sqrt方法将如何影响这个过程，如果可能的话，我正在寻找一些指针

非常感谢！

Answer 1

你可以写T（n）=sqrt（n）⋅T（sqrt（n））sqrt（n）as

T(n) = n1/2 + n3/4 + n7/8 + ...

我们知道∑i=1，。。。，∞2^{-i=1，所以你可以这么说}

T(n) = n1/2 + n3/4 + n7/8 + ... < n + n + n + ...

现在你只需要通过求解n-x来计算和的长度

所以解是T（n）=O（n⋅ log log n）。

抱歉，您正在使用取代基方法寻找解决方案。我从来没有这样做，所以我在这个网站上读了一段描述。

设T（sqrt（n））=k⋅ sqrt（n）⋅ log log sqrt（n）O（sqrt（n））表示常数k。

T(n) = sqrt(n) ⋅ k ⋅ sqrt(n) ⋅ log log sqrt(n) + sqrt(n) + O(sqrt(n)) 
     = k ⋅ n ⋅ log (0.5 log n) + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + log 0.5 + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + O(sqrt(n))
     = O(n log log n)

我希望这有帮助。