0

アルゴリズムの複雑さを再確認して、次の例を見ていました。

int x = 0;
     for ( int j = 1; j <= n; j++ )
        for ( int k = 1; k < 3*j; k++ )
             x = x + j;

このループが最終的に O(n^2) になることはわかっています。私は、内側のループが 3*n 回 ( 3(1+2+...n) ) 実行され、外側のループが n 回実行されると信じています。したがって、O(3n*n) = O(3n^2) = O(n^2) です。

ただし、私が見ているソースは、内部ループの実行を次のように拡張します3(1+2+3+...+n) = 3n^2/2 + 3n/2。誰でも3n^2/2 + 3n/2実行時間を説明できますか?

4

4 に答える 4

1

J ごとに J * 内部ループの 3 回の反復を実行する必要があるため、コマンドx=x+jは最終的に n * 3 * (1 + 2 + 3 ... + n) 回実行され、算術進行の合計は n*(n+ 1)/2 なので、コマンドが実行されます:

3 * n * (n+1)/2 which is equals to (3*n^2)/2 + (3*n)/2

ただし、大きな O は反復回数ではなく、漸近的な尺度に関するものであるため、式 3*n*(n+1)/2 では const を削除する必要があり (それらをすべて 0 または 1 に設定する)、1* になります。 n*(n+0)/1 = n^2

この場合の大きな O の計算に関する小さな更新: 3n(n+1)/2 から大きな O を作成するには、大きな O の場合、N が無限大であることを想像できます。

infinity + 1 = infinity
3*infinity = infinity
infinity/2 = infinity
infinity*infinity = infinity^2

したがって、この後は N^2 になります

于 2013-10-15T20:34:11.523 に答える
1

Big O表記は、アルゴリズムの漸近的な実行時間の上限を示します。低次項や定数因子は考慮されていません。したがって、O(10n 2 ) と O(1000n 2 + 4n + 56) は依然として O(n 2 ) です。

あなたがしていることは、アルゴリズムの操作の数を数えようとすることです。ただしBig O、操作の正確な数については何も述べていません。好ましくない入力で発生する可能性のある最悪の場合の実行時間の上限を提供するだけです。

于 2013-10-15T20:35:03.073 に答える