1

非常相似的复杂性示例。我试图了解这些问题是如何变化的。明天就要考试了：（在这里找到复杂性的任何捷径。

情况1：

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

案例二：

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 4) {}
   N = N / 2;   
   }
}

案例 3：

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 2) {}
   N = N / 2;   
   }
}

非常感谢！

4

2 回答 2

4 
void doit(int N) { 
   while (N) {
     for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

要找到它的 O()，请注意我们每次迭代都将 N 除以 2。因此，（不是侮辱您的智力，而是为了完整性）循环中的最终非零迭代我们将有 N = 1。在此之前的时间我们将有 N=a(2)，然后在此之前 N=a(4)... 其中 0< a < N（请注意，这些是非包含范围）。所以，这个循环总共会执行 log(N) 次，这意味着我们看到的第一次迭代 N=a2^(floor(log(N)))。

我们为什么要关心这个？嗯，这是一个几何级数，有一个很好的封闭形式：

Sum = \sum_{k=0}^{\log(N)} a2^k = a*\frac{1-2^{\log N +1}}{1-2} = 2aN-a = O(N).

如果有人能弄清楚如何让乳胶符号为我正确显示，我将不胜感激。

于 2012-12-12T06:08:55.800 回答
3

正如@NickO 给出的那样，您已经有了数字 1 -的答案O(n)，这是另一种解释。

用 T(N) 表示内循环的外循环次数，并设外循环数为h。注意h = log_2(N)

T(N) = N + N/2 + ... + N / (2^i) + ... + 2 + 1
     < 2N (sum of geometric series)
     in O(N)

3号：是O((logN)^2)

用 T(N) 表示内循环的外循环次数，并设外循环数为h。注意h = log_2(N)

T(N) = log(N) + log(N/2) + log(N/4) + ... + log(1)   (because log(a*b) = log(a) + log(b)
     = log(N * (N/2) * (N/4) * ... * 1)
     = log(N^h * (1 * 1/2 * 1/4 * .... * 1/N))
     = log(N^h) + log(1 * 1/2 * 1/4 * .... * 1/N)    (because log(a*b) = log(a) + log(b))
     < log(N^h) + log(1)
     = log(N^h)                                      (log(1) = 0)
     = h * log(N)                                    (log(a^b) = b*log(a))
     = (log(N))^2                                    (because h=log_2(N))

2号与 3 号几乎相同。

（在 2,3 中：假设j从 1 开始，而不是从 0 开始，如果不是这种情况，@WhozCraig 给出了它永不中断的原因）

于 2012-12-12T06:41:37.653 回答