big-o - 内側のループの反復回数が外側のループの現在の反復によって決定される、入れ子になったループの Big-O とは何ですか?

Question

次の入れ子になったループの Big-O 時間計算量は?

for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        System.out.println("i = " + i + " j = " + j);
    }
}

それでもO(N^2)でしょうか？

Answer 1

ええ、それはまだ O(n^2) です。定数係数は小さくなりますが、それは O 表記には影響しません。

Answer 2

はい。Big-O の定義を思い出してください: O(f(n))は定義により、ある定数kの実行時間T(n) ≤ kf(n)を示しています。この場合、ステップ数は(n-1)+(n-2)+...+0になり、0 から n-1 の合計に再配置されます。これは

T(n)=(n-1)((n-1)+1)/2 .

これを並べ替えると、 T(n)は常に ≤ 1/2(n²) になることがわかります。定義により、したがってT(n) = O(n²)です。

Answer 3

はい、N の 2 乗になります。私が間違っていなければ、実際のステップ数は 1 から N までの合計で、.5*(N - 1)^2 になります。Big O は最高の指数のみを考慮し、定数を考慮しないため、これは依然として N の 2 乗です。