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

思考这个问题的一种方法是独立地查看循环。

这个内部循环嵌套:

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

将执行总共 Θ(i²) 次操作，因为每个循环独立运行 i 次。

现在，让我们看看外层循环:

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

这个循环将最多运行 1 + log₄ i 次，因为在每次迭代中 i 被削减 1/4 倍，这只会发生 1 + log< sub>4 i 次，然后 i 降为零。那么，问题是将完成多少工作。

解决这个问题的一种方法是为完成的总工作写一个简单的递归关系。我们可以将循环视为尾递归函数，其中每次迭代执行 Θ(i²) 工作，然后对大小为 4 的子问题进行递归调用。这给出了这种递归:

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

应用主定理，我们看到 a = 1、b = 4 和 c = 2。因为 log_b a = log₄ 1 = 0 和 0 < c, Master Theorem says (by Case 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²)

(这使用了 sum of an infinite geometric series 的公式)。

希望这对您有所帮助!