algorithm - 这个算法是二次的还是线性的？

Question

我有以下算法:

s=0
for j=1 to n
    k=n
    while k>0
        s++
        k=(int)k/2
    endwhile
endfor

对于我在什么时候分析的内容:

j=1 the while loop executes 1 time
j=2 the while loop executes 2 times
j=3 ...                     2 times
j=4 ...                     3 times
j=5 ...                     3 times
j=6 ...                     3 times
j=7 ...                     3 times
j=8 ...                     4 times

所以我将对外循环求和 (n/2)*n，这会是 O(n^2) 吗？

Answer 1

内部循环将执行 floor(log₂n) 次，所以整个算法有 O(n.long(n)) 复杂性。

可以看到内层循环执行了这个次数

 n    times
-------------
 1      1
 2      2
 4      3
 8      4
16      5
32      6
...    ...
2ⁿ      n+1

从等式两边取log₂()，得到:

 n     log(n+1)

log(n+1) 是 O(log(n))。