シータ（n）以外の2つのループ？

Question

i = n 
while (i >= 1) 
{ 
    for j = 1 to i 
    { 
    Function() <- (O(1)) 
    } 
i = i/2 
} 

答えはTheta（n）ですが、なぜこれがTheta（n）なのかわかりません。

内部ループはn + n/2 + n/4 + ... + 1を実行するので、合計はO（n）になり、外側ループはlogn時間に実行されます。 答えnlognでなければなりません。 なぜこれがTheta（nlogn）の代わりにTheta（n）ですか？私の理解から

Answer 1

あなたの計算は部分的に正しいです。外側のループの複雑さをすでに計算している小さな細部には欠けているだけです。あなたのケースでは、外側ループ内の各反復にそれぞれがかかる時間を計算するだけで、時間の複雑さを計算することを選択しました。そして、それは次のとおりです。

for i=n : O(n) 

for i=n/2: O(n/2) 

. 
. 
. 

for i=1: O(1) 

さて、 インナーループの時間複雑さに基づいて行われた各イテレーションの計算。したがって、合計時間複雑度は、外側ループがどれくらいかかるか（内部ループがかかる時間を含む）であり、各反復を実行するのに要する時間の合計は、 n+n/2+n/4+...+1です。

あなたが参照していた乗算は、外側ループが何回実行され、内側ループが何回実行され、それらを掛けて全体的な時間の複雑さを得るかを知っているときに使用される手法です。代わりに、内側のループがn回実行され、nは外側のループが実行される回数（単純な数学：k * n = k + k + ... + k n回）を追加することもできます。

n + n/2 + n/4 + ... + 1は内部ループが実行される回数ではないので、2番目の方法を使用しているだけです。合計外側のループの各反復で何回実行されているかを調べます。

Answer 2

、内側のループが実行され、N + N/2 + N/4 + ... + 1ので、合計はあなたが必要とするすべてですそれ

O（n）となります。内側ループが実行される回数に外側ループが持つ乗算効果を考慮しています。外側ループの複雑さ自体がO(n)であるという事実は、に加えて、内側ループの複雑さ全体に合わせてとなる可能性があります。合計はn * log nではなく、n + log nです。これはO(n)です。

Answer 3

O（n）であるn + n/2 + n/4 + ... + 1を実行する内部ループ全体については正しいです。外部ループは実行時間がO（log（n））ですが、内部ループの実行時間もlog（n）だけ減少するため、内部ループのランタイムにO（log分割I 2によっては、このようにランタイムはq = 0.5ための幾何学的なシリーズが、これに収束するので、わずかO（N）

Answer 4

n + n/2 + n/4 ... + 1の合計は、常に2*n以下である単純です。

したがって、この関数は2n回以上呼び出されることはなく、複雑さはΘ(n)です。

Answer 5

あなたが正しく指摘したように、内部ループはn + n/2 + n/4 + ... + 1 ≈ 2*n回実行されます。

各コード行が何回実行されるのかを見てみましょう。

i = n     // Executed 1 time 
while (i >= 1)   // Executed approximately log(n) times 
{ 
    for j = 1 to i  // Executed approximately 2*n times 
    { 
     Function()  // Executed approximately 2*n times 
    } 
    i = i/2   // Executed approximately log(n) times 
} 

ので、アルゴリズムの総時間の複雑さは、次のとおりです。Θ(n)と同等です

Θ(1) + Θ(log(n)) + Θ(n) + Θ(n) + Θ(log(n)) 

。