4

私はそのような簡単なループの基本的な概念を理解しているようです...最初のループはO（n）で実行され、内側のループも同様です。どちらもネストされているため、乗算して合計実行時間O（n ^ 2）を取得します。

sum = 0; 
for ( i = 0; i < n; i++ ) 
  for j = 0; j < n; j++ ) 
    ++sum;

物事が切り替わり始めると、私はそれを理解する方法について完全に迷子になります。次の両方の実行時間を計算する方法を誰かが私に説明できますか？また、私がさらに改善するのに役立つ、わかりやすいリファレンスへのリンクもありがたいです。ありがとう！

sum = 0; 
for( i = 0; i < n; i += 2 ) 
  for( j = 0; j < n; j++ ) 
    ++sum;

これから私が集めることができる唯一のことは、内側のループがO（n）で実行されるということです。i + = 2は、本当に私を外側のループに投げ込みます。

sum = 0; 
for( i = 1; i < n; i *= 2 ) 
  for( j = 0; j < n; j++ ) 
    ++sum;

私の試みから...外側のループはO（log（n））、内側はO（n）なので、合計はO（n log（n））ですか？

4

1 に答える 1

2

Big-Oのパフォーマンスについて考える良い方法は、コードの各要素がアイテムを受け取り、nそれらのアイテムに対して実行された計算の数を返す数学関数であると偽ることです。

たとえば、のforような単一のループfor ( i = 0; i < n; i++ )は関数と同等ですi()。ここでi(n) = n、は、入力ごとに1つの計算が実行されることを示しますn。

ネストされたループが2つある場合、

for ( i = 0; i < n; i++ ) 
   for j = 0; j < n; j++ )

次の2つの関数のようになります。

i(n) = n * j(n)
j(n) = n

これらの2つの関数を実行すると、の代わりに使用できるためn*n = n^2、の最終結果が生成されます。j(n)n

これが意味するのは、単一のループのBig-Oを解くことができる限り、それらの解をネストされたループのグループに適用できるということです。

たとえば、2番目の問題を見てみましょう。

for( i = 0; i < n; i += 2 ) 
  for( j = 0; j < n; j++ )

i+=2nアイテムの入力セットの(n0, n1, n2, n3, n4)場合、そのセットの他のすべての要素にのみ触れていることを意味します。のように初期化すると仮定するとi=0、それはのセットにのみ触れていることを意味します(n0,n2,n4)。これは、処理に使用しているデータセットのサイズを半分にしていることを意味し、同等の機能が次のように機能することを意味します。

i(n) = (n/2) * j(n)
j(n) = n

これらを解決することであなたを得ることができます(n/2) * n = (n^2)*(1/2)。これはBig-Oの作業であるため、定数を削除してBig-O値を生成します(n^2)。

ここで覚えておくべき2つの重要なポイント：

  1. Big-Oの計算は、一連のnデータ要素から始まります。forその要素のセットを反復処理するループのBig-Oを決定しようとしている場合、最初のステップは、インクリメンターがルーチンが実際に接触nするデータ要素の数をどのように変更するかを確認することです。for

  2. Big-O数学は数学です。式ごとにfor個別に解くことができる場合は、共通の定義を持つ一連の方程式を解くのと同じように、それらの解を使用して最終的な答えを構築できます。

于 2012-09-12T23:52:00.417 に答える