big-o - 次のループの計算量を求めてください

Question

For n=1 : Inner loop will execute 1 time.
For n=2 : Inner loop will execute 1+2 times.
For n=4 : Inner loop will execute 1+2+4 times.
For n=8 : Inner loop will execute 1+2+4+8 times.

. . .

では、計算の複雑さをどのように見つけることができますか?

私の答えは次のとおりです。内部ループの反復回数 = n+(n/2)+(n/4)+(n/8)+...+(n/n)

Answer 1

総時間計算量は Θ(n) です。これを確認するには、内側のループが反復ごとに Θ(i) を実行し、i が 1、2、4、8、16、32、...、2 ^{log n}の値を取ることに注意してください。等比級数の合計の式を使用してこれを合計すると、次のようになります。

1 + 2 + 4 + 8 + ... + 2 ^{log n} = 2 ^{log n + 1} - 1 = 2 · 2 ^{log n} - 1 = 2n - 1

したがって、行われた合計作業は Θ(n) です。

お役に立てれば！

Answer 2

次のように正式に進めて、実行される命令の正確な数と増加の順序の両方を取得できます。