如何解决递归T(n)= 2T(n ^(1/2))+ log n? [英] How to solve the recurrence T(n) = 2T(n^(1/2)) + log n?

问题描述

我正在尝试查找重复的时间复杂度:

I am trying to find the time complexity for the recurrence:

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

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

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

I am pretty close to the solution, however, I have run into a roadblock. I need to solve:

n ^{(1/2 k )} = 1

n^(1/2k) = 1

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

for k to simplify my substitution pattern. I am not looking for answers to the recurrence, just a solution for k.

推荐答案

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

When you start unrolling the recursion, you get:

这是同一件事，但还有一些其他步骤:

Here the same thing with a few additional steps:

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

Now using the boundary condition for a recursion (number 2 selected as 0 and 1 do not make sense), you will get:

将k代入等式，您将得到:

Substituting k back to the equation you will get:

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

Here are a couple of recursions that use the same idea.

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

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

这篇关于如何解决递归T(n)= 2T(n ^(1/2))+ log n?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！