27

宿題として、次の 8 つのコード フラグメントを与えられ、実行時間を分析して Big-Oh 表記にしました。私が正しい軌道に乗っているかどうか誰か教えてください。 

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

フラグメント1のO（N）を考えています

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

フラグメント 2 についても O(N)

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

フラグメント 3 の O(N^2)

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

フラグメント 4 の O(N)

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

フラグメント 5 の O(N^2) ですが、n * n は私を少し混乱させているので、よくわかりません

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

フラグメント 6 についても O(N^2)

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

フラグメント 7 の O(N^3) ですが、もう一度 n * n が私を失望させています

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

フラグメント 8 の O(N)

4

5 に答える 5

20

フラグメント 5 は O(n^3)、同様にフラグメント 7 は O(n^5)* だと思います。フラグメント 8 の O(log(n)) のようにも見えます。

n * n の問題では、ループの本体を n * n 回実行する必要があるため、O(n^2) になり、それを他のコードの順序と組み合わせます。フラグメント 8 は実際にはカウンターをインクリメントするのではなく 2 倍にするため、問題が大きくなればなるほど、追加の作業が少なくなり、O(log(n)) になります。

*編集:フラグメント 7 は O(n^5) であり、以前考えていた O(n^4) ではありません。これは、jと kの両方が 1 から n * n になるためです。申し訳ありませんが、これを以前にキャッチできませんでした。

于 2008-10-19T18:56:31.897 に答える
7

フラグメント7はO（n ^ 5）であり、現在受け入れられているコメントの主張のようにO（n ^ 4）ではありません。そうでなければ、それは正しいです。

于 2008-10-20T18:18:09.307 に答える
2

ケース 8 の場合、N のいくつかの値の反復回数を書き出してみて、パターンがどのように見えるかを確認してください...それは O(N) ではありません

于 2008-10-19T19:23:07.400 に答える
0

あなたは正しい道を進んでいますが、途中で物事がどのように明確になるかについてのヒントを次に示します。いくつかのコードがあるとします:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

そうです、さまざまなレベルのコードがあるという事実を考慮してください。この例では、これまでに 3 つのレベルしか表示できません。

  1. 0 から n までの外側の for ループ
  2. 0 から 100 までの別の for ループ
  3. としてマークされている内部のコード...

一度にすべてを計算しようとするべきではありません。これは、ほとんどの初心者が何らかの算術エラーを犯す場所です。レベルごとに個別に計算し、それをすべて乗算します。

幸運を！

于 2011-11-14T12:42:29.487 に答える
0

あなたは正しい軌道に乗っているようです。N*N に関しては、どのような効果があると思いますか? これは N の別の因数であるため、より高次になる可能性があります。

警告ですが、このような別の投稿を見たところ、非常に反対票が投じられました。気をつけて。これが投稿です。

于 2008-10-19T18:56:40.430 に答える