大O - 嵌套循环

Question

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)？

Answer 1

如果你这样做

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 2).

如果您打印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