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

我可以将递归关系视为T(square root(n)+n))+1吗？如果是这样，我该如何进一步解决这个问题？

4

2 回答 2

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-part 的细节。

于 2013-10-03T16:41:58.307 回答
0

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

n =2^k 因此 k = log n 。然后 O(log k) 变成 O(loglogn) ...

于 2013-10-03T17:06:05.157 回答