1

最近、プログラミングの面接を受けましたが、次のコードが出てきました。インタビュアーは、それが O(n*n) アルゴリズムであると私に言いましたが、外側のループが実行されるたびに内側のループが実行される回数が少なくなることを考えると、それがどのように行われるかについて私は混乱しています。

それは間違いなく O(n) ではありませんが、なぜ O(n*n) なのですか?

for(int i = 0; i < n; i++)
{
    for(int j = i + 1; j < n; j++)
    {
        ...
    }
}
4

3 に答える 3

3

このように見てください。を初めて使用すると、 99 回iループします。j次に、98、97、96 など、1 つにまで下がります。これは次と同じです。

1 + 2 + 3 + 4 + 5 + ... + n

これらの (三角形の) 数値を合計する簡単な方法は、ガウスに起因する手法を使用することです。

sum = ((n * n) + n) / 2

これで、O(n*n) がはっきりとわかります。

于 2013-09-30T20:14:59.200 に答える
0

i = 0 の場合: 内側のループが 99 回実行
されます。 i = 1 の場合: 内側のループが 98 回実行
されます。 i = 2 の場合: 内側のループが 97 回実行
されます
。
.
.
for i = 99: 内側のループは 0 回実行されます

EOP の数を数える場合、たとえば #(EOP) := S とすると、S = 0 + 1 + 2 + 3 + .... + 99 なので S = (99* (99 + 1)) / 2 <= > S = (99*99 + 99) / 2 => S <= 1/2 * 99^2 + 99 <=> S <= 99^2 + 99 <=> S <= 99^2 + 99^2 <=> S <= 2* 99^2 なので、n = 99 で c = 2 とすると、S <= c*n^2 となり、S の次数は n^2 になります。あなたがコミットしたプログラムフラグメントは、そのためn ^ 2の順序を持​​っています

于 2013-09-30T20:25:29.283 に答える