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

本文介绍了如何解决递归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(n1/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))