2 
int a = 0;  //1 unit
for (int b = 0; b < N; b++) // (1 + N + N) = 2n + 1
    for (int c = b+2; c > 0; c--) //2 + (N+1) + N = 2N+3
        a += b*c; //3 units

収量:1 + (2n+1)(2n+3) = 4n^2+8n+4

私はアルゴリズム分析が初めてで、これが正しいとは 100% 確信が持てません。誰かが私を助けて、私がこれを正しく行っているかどうかを教えてもらえますか? そうでない場合は、どこが間違っていたかを指摘してください。

ほとんどの場合、最悪の場合の実行時間を計算しました4n^2+8n+4

4

5 に答える 5

1

内側のループは、外側のループの b の値ごとに b+2 回実行されます。したがって、内側のループが実行される合計回数は (2 + 3 + 4 + .... + (N+2)) に等しくなります。毎回 3 単位の作業を実行します。したがって、内側のループが実行される合計時間は [ ((N+2) (N+3)/2 ) - 1 ] * 3 です。

しかし、一般的に実行時間は漸近的に測定され、これは Big O (N ^ 2) になります。

于 2013-06-10T05:54:03.710 に答える
1

一般に、big O Notationを使用する場合、係数は無視され、アルゴリズムは最も急速に成長する関数によって分類されます。この場合、O(n)ネストされた 2 つのループがあります。ネスティングは乗法的であり、アルゴリズムにO(n²)別名「二次」複雑さを与えます。Big O 表記法と計算の複雑さに関するウィキペディアの記事は、さらに読むための出発点になるかもしれません。

于 2013-06-10T05:54:08.967 に答える
1

内側のループのステートメントが 3 ユニットかかると言いたい場合、内側のループは ( b + 2 ) * 3 ユニットかかります。ここで、b の範囲を 0 から N - 1 にして合計すると、次のようになります。

( 0 + 2 ) * 3 + ( 1 + 2 ) * 3 + (2 + 2) * 3 + ... + ( 2 + N - 1 ) * 3

= 3 * (2 + 3 + 4 + 5 + ... + ( N + 1 ) )

= 3 * ( ( 1 + 2 + ... + N+1 ) - 1)

= 3 * ( ( ( N +1 ) ( N + 2 ) / 2 ) - 1 )

= 3 * (N^2 + 3*N + 2 - 2) / 2

= 3/2 * N^2 + 9/2 * N

ループ ヘッダーで実行された操作を操作として数えていないことに注意してください。通常、これは行われません。実際、通常は、最も多く実行された最もコストのかかる演算 (この場合は乗算) をカウントするだけです。

ちなみに、最初の n 個の整数の和が n ( n+ 1 ) / 2 であることを利用しました。

于 2013-06-10T05:55:03.203 に答える
0

あなたの例：

int a = 0;  // 1

for (int b = 0; b < N; b++) // 1 + (N+1) + N
{
    for (int c = b+2; c > 0; c--) // 1 + (((N+2)*(N+3)/2)+1) + ..) * N
    {
        a += b*c; // 3 * ((N+2)*(N+3)/2) * N
    }
}

計算すると、次のようになります。

= 1 + 1 + (N+1) + N + 1 + [(((N+2)*(N+3)/2)+1) + ((N+2)*(N+3)/2)) * N] + [3 * ((N+2)*(N+3)/2) * N]

= 4 + 2 N + 1/2 N^3 + 3 N^2 + 11/2 N + 4 + 9 N + 15/2 N^2 + 3/2 N^3

= 8 + 33/2 N + 21/2 N^2 + 2 N^3

私たちに与えるO(N^3)

于 2013-06-10T06:28:30.163 に答える