问题描述
我正在尝试查找重复的时间复杂度:
I am trying to find the time complexity for the recurrence:
我非常接近解决方案,但是,我遇到了一个障碍.我需要解决:
I am pretty close to the solution, however, I have run into a roadblock. I need to solve:
为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)= 2T(n ^(1/2))+ log n?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!