0

（誰かが何かを言う前に はい、これは宿題でしたが、私はすでにそれを提出し、取り戻しました。明日のテストのためにこれを理解したいだけです。）

問題は、コード スニペットの実行時間と大きな O を計算することでした。ビッグオーの罰金を計算できますが、実行時間をどのように決定できるかわかりません。基本的に私が理解していないのは、実行時間を計算する方法です 

for(i=0; i < n; i++){
    SomeJavaStatment;
    for(j=0; j < 2 * n; J+= 2){ 
        SomeJavaStatment;
        SomeJavaStatment;
}
}

正解は Big O(n^2) でした。正解でしたが、実行時間がわからず、4n^2+5n+2 が正解でした。

誰かがその答えにたどり着く方法を説明していただければ幸いです。

4

2 に答える 2

7

実行時間をそのように決定する必要があるとは思いませんが、

 //assignment to i takes 1 operation    
 for(i=0; i < n; i++){ // i++ is executed n times, i < n is executed (n+1) times
    SomeJavaStatment; // n times

    //assignment to j takes 1 operation
    for(j=0; j < 2 * n; j+= 2){  // j+=2 is executed n*n times, j < 2*n is executed n*(n+1) times
        SomeJavaStatment; // n * n times
        SomeJavaStatment; // n * n times
    }
 }

合計すると、1 + n + (n+1) + n + n + (n*n) + (n+1)*n + (n*n) + (n*n) = 4 * n^2 + 5*n + 2:)

于 2012-04-03T21:29:58.943 に答える
0

Big O は、関数の上限を表します。関数は Big O(n^2) であるだけでなく、厳密な境界もあります ( の任意の値に対してn、関数の実行時間はまったく同じです)。正確なタイト バウンドを手動で計算することも、合計として を表すこともできます4n^2+5n+2。

于 2012-04-03T21:34:09.597 に答える