迭代算法的时间复杂度？

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次迭代.序列类似于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)双精度k.

所以算法的时间复杂度是?(n).