algorithm - 迭代算法的时间复杂度？

Question

这是算法:我认为它的时间复杂度是 O(nlogn) 但我不确定

k=1;
while (k<=n) do      
    j=1;
    while (j<=k) do        
        sum=sum+1;
        j=j+1;
    k=k*2;

Answer 1

内层循环第一次执行1次迭代，第二次执行2次迭代。序列就像 1、2、4、8、16、32，... 只要它小于或等于 n .该序列可能有 Θ(log(n))元素，但其总和为 Θ(n) .这是因为

1 + 2 + 4 + ... + 2^k = 2 * 2^k - 1

我们知道n/2 < 2^k <= n .所以执行内循环Θ(n)次并且每个内部循环执行都需要恒定数量的指令。

剩下的代码就是log(n)分配给 j = 1和 log(n) double k .

所以该算法的时间复杂度为Θ(n) .