分析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））。