math - 如何解决递归T(n) = 2T(n^(1/2)) + log n？

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

3年前关闭。




Improve this question




我试图找到重复的时间复杂度:

T(n) = 2T(n^1/2) + log n

我非常接近解决方案，但是，我遇到了障碍。我需要解决:

n^(1/2k) = 1

for k 来简化我的替换模式。我不是在寻找复发的答案，只是为 k 寻找解决方案.

Answer 1

当您开始展开递归时，您会得到:


同样的事情，还有一些额外的步骤:



现在使用递归的边界条件(数字 2 选择为 0 和 1 没有意义)，您将得到:



代入 k回到等式，你会得到:



这里有几个使用相同想法的递归。

T(n) = T(n^1/2) + 1

T(n) = T(n^1/2) + O(loglog(n))