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 倍，并且在 i 下降到零之前只能发生 1 + log ₄ i 次。那么，问题是要完成多少工作。

解决这个问题的一种方法是为完成的总工作编写一个简单的递归关系。我们可以将循环视为尾递归函数，其中每次迭代都执行 Θ(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 ² )

（这使用了无限几何级数之和的公式）。

希望这可以帮助！

Answer 2

The running time is O(n^2), and the number of times that total is incremented is asymptotic to n^2/(1-1/16) which is about 1.067 n^2. The recurrence is going to be

T(n) = n^2 + T(n/4)
     = n^2 + n^2/16 + T(n/16)
     = n^2 (1 + 1/16 + 1/16^2 + ...)
     = n^2 / (1 - 1/16)

Answer 3

此代码片段：

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

相当于这个：

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

因此，有条不紊地（经过经验验证），您可以使用 Sigma 表示法获得以下信息：*

非常感谢WolframAlpha。