1

BigOh を計算するための HW 割り当てがありますが、ループ内の反復で問題が発生しています。

ループ:

public static int fragment4b(int n){
    int sum = 0;
    for(int i = 1; i <= n*n; i++)         
        for(int j = i; j>= 1; j /=2)        
            sum +=j; 
}

外側のループが O(n*n) であることは理解していますが、内側に何か問題があると感じています

したがって、内側のループには O( (ln(i)/ln(2)) + 1 ) があることがわかります。または私は間違った木を吠えています

4

2 に答える 2

3

sum+= j内側のループはステートメントを正確に繰り返しますここに画像の説明を入力

外側のループは、この N^2 回を繰り返しています。

したがって、操作の合計数は、次のように 1 から N^2 までの内部ループの合計です。ここに画像の説明を入力

そしてそれはここに画像の説明を入力

編集：ログを取るときは、その床を取ります。

于 2013-10-02T23:00:41.157 に答える
2

次のように実行時間を計算します。

T = log1 + log2 + log3 + ... + log(n^2)

上記の式では、最初の項は外側のループの最初の反復の実行時間、2 番目の項は 2 番目の反復の実行時間などです。

次のことは明らかです。

T < log(n^2) + log(n^2) + ... + log(n^2) = 2(n^2)logn = O(n^2logn))

したがって、実行時間は によって制限されO(n^2logn)ます。

于 2013-10-02T22:40:04.303 に答える