分析while循环

Question

考虑嵌套循环：

for i from 1 to n 
    k=i; 
    while(k>0) 
    do c operations; 
    k=floor[k/2]; 
    end while 
end for 

计算操作 我需要知道多少次迭代while循环第一，我想通的NUM是（可能是错的）： K = 1， K =地板[1/2 * I]，K =地板1/4 .... K =地板[（1/2）^ *ĴI]，K = 1。我知道最后的k将永远是1的权利？并且while循环内的操作数是j + 1？我不知道如何解决j。 有人可以帮忙吗？

Answer 1

while循环log（i）次循环。所以在for循环的一次迭代中，完成了c * log（i）操作。所以在总：

C *日志（1）+ C *日志（2）+ C *日志（3）+ ... + C *的log（n）

如果你需要的渐近运行时间：那就是O（n log（n））。