algorithm - このアルゴリズムの実行時間の複雑さは?

Question

このアルゴリズムの時間計算量は?

sum = 0
i = 1

while (i < n) {

    for j = 1 to i {
        sum = sum + 1
    }

    i = i*2;
}

return sum

whileループがであることは知っていますが、ループO(logn)の複雑さはどのくらいforですか? O(n)それとも？O(logn)_

Answer 1

これを分析する 1 つの方法は、内側のループの反復回数を数えることです。最初の繰り返しで、ループが 1 回実行されます。2 回目の反復では、2 回実行されます。3 回目の反復で 4 回、4 回目の反復で 8 回、より一般的には^k回目の反復で 2k 回実行されます。これは、内側のループの反復回数が次の式で与えられることを意味します。

1 + 2 + 4 + 8 + ... + 2 ^r = 2 ^{r + 1} - 1

ここで、r は内側のループが実行される回数です。ご指摘のとおり、r はおおよそ log n です。つまり、この合計は (おおよそ)

2 ^{log n + 1} - 1 = 2(2 ^{log n} ) - 1 = 2n - 1

その結果、O(n) 内のすべての反復にわたって内側のループによって実行される合計作業。プログラムは外側のループを実行して合計 O(log n) の作業を行うため、このアルゴリズムの合計実行時間は O(n + log n) = O(n) です。O(log n) 項は、純粋に外側のループの保守で行われる作業の総量であり、O(n) 項は、純粋にループによって行われる作業の総量であるため、これらの項を一緒に乗算しないことに注意してください。内側のループ。

お役に立てれば！