ビッグO表記の宿題-コードフラグメントアルゴリズム分析？ [閉まっている]
https://stackoverflow.com/questions/216796
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
宿題については、分析のために次の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++;
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++;
O（N ^ 2）フラグメント6も同様
//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）
解決
フラグメント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 ^ 4）ではなくO（n ^ 5）です。これは、j とk の両方が1からn * nになるためです。申し訳ありませんが、これは以前に見つけられませんでした。
他のヒント
フラグメント7はO（n ^ 5）であり、現在受け入れられているコメントが主張しているO（n ^ 4）ではありません。それ以外の場合は正しいです。
ケース8の場合、Nのいくつかの値の反復回数を書き出して、パターンがどのように見えるかを確認してください... O（N）ではありません
あなたは正しい道を進んでいるようです。 N * Nに関して、どんな効果があると思いますか？これはNのもう1つの要因であるため、高次になる可能性があります。
ただの警告ですが、私はこのような別の投稿を見つけました。注意してください。 こちらは投稿です。
あなたは正しい道を歩んでいますが、ここで、物事がどのように明確になるかについてのヒントを示します。いくつかのコードがあるとします：
for(i = 0; i < n; i++) {
for(j = 0; j < 100; j++){....}
}
そうです、異なるレベルのコードがあるという事実を考慮してください。この例では、これまでに3つのレベルしか表示できません：
- 0-nから始まる外側のforループ
- 0から100までの別のforループ
-
...としてマークされた内部コード
一度にすべてを計算しようとしてはいけません。これは、ほとんどの初心者が何らかの算術エラーを起こす場所です。レベルごとに個別に計算し、すべてを乗算します。
がんばって！
