1

*22番目のループで何が起こるか混乱しています。最初のループがn反復を行い、2 番目のループが増加することを理解している*2ため、反復の回数を決定する方法がわかりません。のように、2 番目のループの反復を+2行うと思います。n/2

for (int count = 0; count < n; count ++)
{
    for (int count2 = 1; count2 < n; count2 = count2 * 2)
    {
        System.out.println(count, count2);
    }
}
4

1 に答える 1

3

したがって、より単純なケースが得られます。

for (int count = 0; count < n; count ++)
{
    for (int count2 = 1; count2 < n; count2 ++)
//                                   ^^^^^^^^^
    {
        System.out.println(count, count2);
    }
}

ここでは、外側のループが実行n時間、内側のループが実行n時間であるため、単純に乗算nしnて O(n 2 ) を取得します。(このコード フラグメントの内側のループが時間だけ実行されるという事実はn-1、順序に違いはありません。)

count2問題は、毎回倍増するあなたの例では、内側のループの関数は何ですか? 内側のループの実行時間の関数を呼び出しましょうf(n)。したがって、big-O は O(nf(n)) になります。

内側のループを見てみましょう。1time if n=1..2、2times if n=3..4、3times if nis upto 8、4times if nis upto 16、5times if nis uptoを実行し32ます。2=>1、4=>2などをマッピングするこの関数は何8=>3ですか?

注意すべきことは2 = 2^1、、、、4 = 2^2など8 = 2^3です16 = 2^4。あなたが望むのは、2 の累乗でレイズすることの反対であり、これは 2 を底とする対数です (ただし、大きな O の場合、対数は問題になりません)。

したがってf(n) = log(n)、O(n log(n))があります。

編集: 何が起こっているかを把握する最も簡単な方法は、プログラムをさまざまな値で実行することですn。たとえば、n=8次の出力が得られます。

(0,1)、(0,2)、(0,4)
(1,1)、(1,2)、(1,4)
(2,1)、(2,2)、(2,4)
(3,1)、(3,2)、(3,4)
(4,1)、(4,2)、(4,4)
(5,1)、(5,2)、(5,4)
(6,1)、(6,2)、(6,4)
(7,1)、(7,2)、(7,4)

反復回数 = n log2(n) = 8 * 3 = 24. これは、nが のべき乗である正確な関係です2。それ以外の場合、関係は正確ではありません。たとえば、同じ出力が得られますが (最終行のバー)、コードはまだ O(n log(n)) です。これは、内側のループの反復回数が になるようにn=7定数 を選択できるためです。k=2<= k n log(n)

于 2013-09-18T22:51:23.563 に答える