依赖嵌套循环的时间复杂度

Question

我看过类似的问题，也问过同学，但我对答案有疑问。

这个算法的时间复杂度是多少？

for (i = 1; i < n; i *= 2)
    for (j = 1; j < i; j *= 2)
        \ c elementary operations

有人告诉我 O(log(n))^2 但从我阅读和尝试的内容来看，它看起来像 O(log(n)*log(log(n)))。有帮助吗？

Answer 1

对于外循环的每次迭代，内循环自身重复 log_2(i) 次。

那就总结一下吧

(1) T(n) = log_2(1) + log_2(2) + log_2(4) + log_2(8) + ... + log_2(n)
(2) T(n) = sum { log_2(2^i)    | i=0,1,..,log_2(n) }
(3) T(n) = sum { i * log_2(2)  | i=0,1,...,log_2(n) } 
(4) T(n) = 0 + 1 + ... + log_2(n)
(5) T(n) = (log_2(n) + 1)(log_2(n))/2
(6) T(n) is in O(log_2(n)^2)

解释：

(1) -> (2) 只是求和 shorthand
(2) -> (3) 是因为 log(a^b) = blog(a)
(3) -> (4) log_2(2) = 1
(4) -> (5) Sum of arithmetic progression
(5) -> (6) 给出渐近符号

依赖嵌套循环的时间复杂度

Time Complexity of dependant nested loop

nested

time-complexity