5 
void bar(int N){
  int c=0;
  for (int i=0; i<N*N; i++)
    for (int j= i; j< N; j++)
      c++;
}

上面的外部（和内部）循环永远不会超过 N。这是否意味着大 O 为 N*N（外部为 N，内部为 N/2）？

4

2 回答 2

7

如果你这样做

for (int i = 0; i < N; i++)
  for (int j = i; j < N; j++)
    …

您将首先在内循环中迭代 N 次，然后是 N-1，然后是 N-2，等等，总和为 N(N-1)/2。该循环以 O(N²) 运行，即外循环的平方。

在您的情况下，您的代码相当于

for (int i = 0; i < N; i++)
  for (int j = i; j < N; j++)
    c++;

因为对于每个正整数我们都有 N² ≥ N 并且编译器应该足够聪明地注意到如果 i 大于 N 继续运行外循环是没有意义的。所以复杂度确实是 O(N²)。

如果您打印N并c在程序运行后，您会注意到当N翻倍时，c几乎乘以 4 (2²)：

N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176
于 2013-06-23T11:06:34.477 回答
0

要正式了解迭代次数和增长顺序：

在此处输入图像描述

于 2014-03-17T22:05:43.627 回答