algorithm - 指数関数的に減衰するループのランタイム?

Question

関数nへの入力は、任意の整数にすることができます。

i = n, total = 0; 
while (i > 0) {      
 for (j=0; j<i; j++) 
   for (k=0; k<i; k++) 
     total++;      
 i = i/4; 
} 

この関数の時間計算量は?

Answer 1

これについて考える 1 つの方法は、ループを個別に調べることです。

この内側のループ ネスト:

for (j=0; j<i; j++) 
   for (k=0; k<i; k++) 
     total++;

各ループは独立して i 回実行されるため、合計で Θ(i ^{2 ) 操作が実行されます。}

では、外側のループを見てみましょう。

while (i > 0) {      
    /* do Theta(i^2) work */   
    i = i/4; 
} 

このループは、最大で合計 1 + log ₄ i 回実行されます。これは、反復ごとに i が 1/4 の係数でカットされるためです。これは、i がゼロになる前に1 + log _{4 i 回だけ発生する可能性があります。}問題は、どのくらいの作業が行われるかということです。

これを解決する 1 つの方法は、完了した作業の合計に対する単純な繰り返し関係を作成することです。ループは、各反復が Θ(i ² ) を実行し、サイズ 4 の部分問題で再帰呼び出しを行う末尾再帰関数と考えることができます。これにより、次の再帰が得られます。

T(n) = T(n / 4) + Θ(n ² )。

マスター定理を適用すると、a = 1、b = 4、および c = 2 であることがわかります。log _b a = log ₄ 1 = 0 および 0 < c であるため、マスター定理は (ケース 3 により)ランタイムがΘ(n ² )。したがって、行われた総仕事量は Θ(n ² ) です。

これを考える別の方法があります。ループの最初の反復では、n ²個の作業が行われます。次は (n / 4) ² = n ² / 16 です。次は (n / 64) ² = n ² / 256 です。実際、ループの反復 x は n ² / 16 ^xの作業を行います。したがって、行われた総仕事量は次のように与えられます。

n ² (1 + 1 / 16 + 1 / 16 ² + 1 / 16 ³ + ...)

≤ n ² (1 / (1 - 1/16))

= Θ(n ² )

(これは、無限幾何級数の和の式を使用します)。

お役に立てれば！