7

Big O表記を使用して、forループの複雑さを理解しようとしています。私は以前に他のクラスでこれを行いましたが、これは実際のアルゴリズムに基づいているため、他のクラスよりも厳密です。コードは次のとおりです。

for(cnt = 0, i=1; i<=n; i++) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

と

for(cnt = 0, i=1; i<=n; i*=2) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

最初のループはリストをn回通過するため、O（n）の複雑さであることがわかりました。2番目のループに関しては、私は少し迷っています。テストされるnごとにi回ループを通過していると思います。私は（誤って）これは、ループが評価されるたびにループがO（n * i）であることを意味すると想定しました。私の仮定に欠けているものはありますか？cnt++は定数時間であることを私は知っています。

分析にご協力いただきありがとうございます。各ループは独自のスペースにあり、一緒ではありません。

4

3 に答える 3

9

最初の例の外側のループは時間を実行nします。外側のループの反復ごとに、内側のループは実行i回数を取得するため、全体的な複雑さは次のように計算できます。最初の反復に1つ、2番目の反復に2つ、3番目の反復に3つ、というように、nさらにn- 3回目の反復。

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2)

2番目の例は注意が必要です。i反復ごとに2倍になるため、外側のループは1Log2(n)回だけ実行されます。nそれがの累乗であると仮定すると2、内側のループの合計は次のようになります。

1+2+4+8+16+...+n

これは2^Log2(n)-1 = n-1複雑さのためO(n)です。

2の累乗ではないsの場合n、正確な反復回数は(2^(Log2(n)+1))-1、ですO(n)。

1      -> 1
2..3   -> 3
4..7   -> 7
8..15  -> 15
16..31 -> 31
32..63 -> 63

等々。

于 2012-09-11T18:39:18.823 に答える
0

うまくいけば、これは宿題ではありませんが、少なくともここで試みたことがわかります。それで、これについての私の見解は次のとおりです。

cntはn*（n + 1）/ 2倍に増分され、両方のループのセット全体がO（n ^ 2）になります。2番目のループは平均してO（n / 2）、つまりO（n）です。

于 2012-09-11T18:37:31.503 に答える
0

最初の例はO（N ^ 2）であり、ネストされたループのBig-Oとは何ですか。ここで、内側のループの反復回数は、外側のループの現在の反復によって決定されます。重要なのは、内側のループのラウンド数がnに依存していることに注意することです。

2番目の例は、外側のループが線形とは異なるスケールでインクリメントされているため、O（n log n）である可能性があります。対数の複雑さの場合の例については、二分探索を見てください。2番目の例では、外側のループはO（log n）で、内側のループはO（n）であり、これらを組み合わせてO（n log n）の複雑さを与えます。

于 2012-09-11T18:40:12.287 に答える