1. ホーム
  2. big-o

[解決済み] ネストされたループのうち、内側のループの反復回数が外側のループの現在の反復回数によって決定されるBig-Oとは何ですか?

2022-02-24 08:23:45

質問

以下の入れ子ループの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) それでも?

どのように解決するのですか?

定数係数が小さくなっても、O(n^2)の表記には影響しない。