2

次のコードスニペットがあります。

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

複雑さはO(n^2)ですが、内部ループの複雑さについてもう少し掘り下げたい場合は、それでしょう(n (n-1))/2か(n-1)!？

4

6 に答える 6

7

はい、O（n ^ 2）ですが、実際には0 + 1 + ... + n-1 = n（n-1）/ 2 = O（n ^ 2）であり、（n-1）ではありません。

于 2010-02-10T02:07:36.717 に答える
3 
time = n*(n-1)/2
     = (n*n - n)/2

big-O表記は上限であるため、低次の項（-n）と定数係数（1/2）の両方が削除され（時間の上限を表すのに重要ではないため）、big- O表記、O(n*n)よく知られていO(n^2)ます。

于 2010-02-10T02:12:29.547 に答える
1

時間内に実行されるアルゴリズムを持つことができます

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

そしてそれはまだO（n ^ 2）です。

Oよりもアルゴリズム実行時間のより良い説明を見つけることは未解決の問題です。

于 2010-02-10T02:47:50.053 に答える
0

まず第一に、を(n-1)!意味し(n-1)(n-2)...(2)(1)ます。これは明らかにあなたがここで望んでいることではありません。

実際の反復回数を数えると、それは0 + 1 + 2 + ... + (n-2) + (n-1)です。n合計には項があり、各ペアの平均値がであるようにそれらをペアにすることができることに注意してください(n-1)/2。（最高と最低、2番目に高いと2番目に低いなどをペアにします。）n奇数の場合、ペアにできないものが残りますが、便利なことにその値も(n-1)/2です。したがって、項があり、nすべての項の平均は(n-1)/2、であるため、合計はn(n-1)/2です。

さて、大きなO表記の場合、反復回数は正確には関係ありませんn。非常に大きい場合の制限を知りたいだけです。反復回数は。と書くことができることに注意してください(1/2)n^2 - (1/2)n。非常に大きいn場合、n^2用語は方法であり、用語よりもはるかに大きいため、n用語を削除しnます。それは私たちにを残すだけですが(1/2)n^2、大きなO表記の別の規則は、定数係数を気にしないということです。したがって、それはO（n ^ 2）であると書くだけです。

于 2010-02-10T02:43:40.340 に答える
0

big-O表記に関する限り、定数は関係ありません。

于 2010-02-10T02:06:47.717 に答える
0

計算(n(n-1)/2)したのは、コードの正確な反復回数です。Oが大きいかどうかという観点から時間計算量を求められた場合、かかった時間を表すのに十分な大きさの見積もりを出します。

言い換えると、いくつかの場合、正確な反復回数よりも大きくなるようなものを見つけるTHE SMALLEST power必要があります。あなたの場合、たまたまそうです。次に、時間の複雑さです。nk (k>0)k * n^powerk1power2O(n^power)

于 2010-02-10T02:11:48.880 に答える