循环的运行时间呈指数衰减？

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 ₄次,因为在每次迭代时我被减少1/4,这在i降到零之前只能发生1 + log ₄次.那么,问题是将完成多少工作.

解决此问题的一种方法是为完成的总工作写一个简单的递归关系.我们可以将循环视为尾递归函数,其中每次迭代都使Θ(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/4)² = N ² /的1/16.下一确实(N/64)² = N ² /256个工作.事实上,迭代X循环会做ñ ² /16个^X的工作.因此,完成的工作总数由

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

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

=Θ(n ²)

希望这可以帮助!