迭代算法的时间复杂度？

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) k 的两倍。

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

Answer 2

// code                 | max times executed
k=1;                    | 1
while (k<=n) do         | log n
    j=1;                | log n
    while (j<=k) do     | log n * n
        sum=sum+1;      | log n * n
        j=j+1;          | log n * n
    k=k*2;              | log n

所以 O 复杂度似乎是 n log n。

迭代算法的时间复杂度？

Time complexity of the iterative algorithm?

algorithm

time

time-complexity