big-o - Big 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 を超えることはありません。これは、Big 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 になります。このループは、外側のループの 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てプログラムを実行すると、 when Ngets cdoubled がほぼ 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