java - コードの複雑さ = n^2?

Question

次のコードの複雑さは?

int data[] = { /* some numbers here */ };
n = data.length;

int lessThanCounter = 0;
for (int i=0; i<n; i++)
    for (int j=n-1; j>i; j--)
        if (data[i]<data[j]) lessThanCounter++;

私の計算では O(n^2) です - これは正しいですか?

Answer 1

外側のループがn何回も実行されると、最初の乗数は になりnます。

内側のループは を実行n-1しn-2ます。0これは とほぼ同等(n-1)/2です。

n * (n-1)/2したがって、これは時間を実行し、教えられているbig-Oのフレーバーに応じて異なりますO(n^2)。O(n^2/2)

NB: 私は、O(n^2/2)Big Oh を適切に理解していない多くの教育機関に迎合することを追加しました。明らかに誤解を招くような間違いをお詫び申し上げます。

NBB: 明確でない場合は、O(n^2/2)投稿したときに間違っていることを知っていました。ただし、教師が答えにそれを入れることを期待している場合は、そうしてください。なぜそれが間違っているのかを説明しようとして進歩することはまずありません。

Answer 2

それは正解です。内側のループの本体は、n-1外側のループの最初の繰り返しで 回実行さn-2れ、2 番目の繰り返しで 回実行され、n繰り返し回数回になるまで繰り返されn-n = 0ます。したがって、n-1 + n-2 + ... + 0 = (n-1)*n/2 = (n^2-n)/2合計で実行された回数であり、実際にはO(n^2).

Answer 3

アルゴリズムの実行時間が O(n^2) であることを証明するには、最初のループで

for(int i=0:i<n;i++)

i は 0 から n に移動し、2 番目のループ:

for(int j = n-1;j>i;j--)

j は n-1 から i まで

data[i]、data[j]およびの比較lessThanCounter++はすべて一定時間で実行されますO(1)

したがって、次の合計があります。

 $\sum_0^{n}(\sum_{n-1}^{i})1$.

あなたが得る内部総和を排除することによって: i+n+2

（n + i + 2）の合計（i = 0からn-1）が得られました

次に (n+2) の合計 (i=0 から n-1) + i の合計 (i=0 から n-1) = (n+1)*(n+2) + n(n+1)/ 2

これは明らかに O(n^2) です

それが役に立てば幸い！

Answer 4

あなたは絶対に正しいです、ループ内のループはO（n ^ 2）です