12

もう1つのBigO表記の質問...次のコードのBigOとは何ですか。

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           for (int k = 0; k < n; k++){
              count++;
           }
        }
     }

私の考え：それを分解すると、外側のループはO(log2(n))であると思います。次に、内側のループのそれぞれが、質問1O(n)の結果になりO(n^2 * log2(n)) ます。それは正しいですか？

質問2：ネストされたループを組み合わせる場合、各ループのBig Oを複数回実行するのと同じくらい簡単ですか？

4

4 に答える 4

14

ループカウンターが相互に依存していない場合は、常に内側から外側に向かって作業することができます。

最も内側のループは、jとiの値に関係なく、n回ループするため、常に時間O（n）を要します。

2番目のループが実行されると、O（n）回の反復が実行され、各反復でO（n）が実行されて最も内側のループが実行されます。これには時間O（n 2）がかかります。

最後に、外側のループが実行されると、反復ごとにO（n 2 ）が機能します。また、1に達する前にnを2で除算する必要がある回数に等しい回数実行されるため、O（log n）回の反復でも実行されます。したがって、合計作業量はO（n 2 log n）になります。

一般に、ループの境界は相互に依存している可能性があるため、ループを単純に乗算することはできません。ただし、この場合、依存関係がないため、ランタイムを乗算するだけで済みます。うまくいけば、上記の理由がこれがなぜであるかを明らかにするでしょう-それは、各ループがどれだけの作業を行い、何回それを行うかを考えて裏返しに作業すると、ランタイムが一緒に乗算されるためです。

お役に立てれば！

于 2013-01-24T21:05:37.773 に答える
3
  1. はい、これは正しいです。外側のループはlogN、他の2つはNそれぞれ、合計でO(N^2*LogN)
  2. 単純なケースでは、そうです。より複雑なケースでは、ループインデックスが他のインデックスで示される番号で始まる場合、計算はより複雑になります。
于 2013-01-24T21:05:24.453 に答える
2

これに少し（注：少し）より正式に答えるために、たとえばT(n)、アルゴリズムを完了するために必要な時間（または操作の数）です。次に、外側のループの場合T(n) = log n*T2(n)、ここで、はループ内T2(n)の操作の数です（定数は無視されます）。同様に、T2（n）= n * T3（n）= n*nです。

次に、次の定理を使用します。

f 1（n）= O（g 1（n））およびf 2（n）= O（g 2（n））の場合、f 1（n）×f 2（n）= O（g 1（n ） × g2 （n））
（ソースと証明）

これにより、T（n）= O（n 2 logn）が残ります。

「ネストされたループの組み合わせ」は、この定理の単なる応用です。問題は、各ループが使用する操作の正確な数を把握することである可能性があります。この場合、これは単純です。

于 2013-01-24T21:28:35.753 に答える
0

ループを忠実に模倣するために、SigmaNotationを使用して正式に進めることができます。

ここに画像の説明を入力してください

于 2014-04-15T12:51:01.507 に答える