下面的递归函数的时间复杂度是多少

Question

int Do(int n) 
{ 
if(n<=2) 
    return 1; 
else 
return(Do(floor(sqrt(n))+n); 
} 

我可以把递归关系看作是T(square root(n)+n))+1？ 如果是这样，我该如何进一步处理这个问题？

Answer 1

当它在你的问题中时，递归不会终止（至少在理论上，这就是你可能在谈论的内容）。原因：n + floor(sqrt(n))大于n。

我想你的意思是return Do(floor(sqrt(n))) + n。我继续回答这个问题的一般考虑，但要小心：你必须填写一些空白！

我会有关的运行时间的问题分成两个部分：

• 最重要的是：有多少递归，直到基本情况？
• 如何结合所有的递归？

号递归：写n作为2的幂（即n=2^(ld n)，其中ld表示用于基体2的对数）。取n分别为平方根。 2^(ld n)将指数减半。为了达到基本情况，我们必须将指数减半，直到小于1。这导致了一个问题：我们需要多少次将ld n减半，直到达到<= 1。这个问题的答案大致为ld ld n。也就是说，我们有大致ld ld n递归直到基本情况。

现在，我们做的递归和总结：

T(n) = T(2^(ld 2)) 
    = T(2^((ld 2)/2)) + 1 
    = T(2^((ld 2)/4)) + 1 + 1 
    = ... 
    = T(2^((ld 2)/(2^(ld ld 2)))) + sum(1, i=0...(ld ld 2)-1) 
    = 1 + (ld ld 2) - 1 

它仍然简化之和调整为floor双组分的细节。

Answer 2

取任意数字n和n = 2^k。 n的平方根意味着你指数的一半。因此，只能有O（log k）平方根。

因此n = 2^k k = log n。那么O（log k）变成O（loglogn）...