算法复杂度分析C++

Question

如果我有这样的循环怎么办

for( int i=2 ; i<n ; i=i*i ){ 
    .
    .
}

这样一个循环的复杂度是多少？

Answer 1

如果循环从 0 开始，这是 OP 的初始问题：

除非n<=0，否则将是一个无限循环。 i从0开始，0*0=0。如果 n<=0，循环将不会执行，因为循环进入时条件 i<n 不满足。

Answer 2

循环将执行只要：

2^{2^{iteration - 1}} < n

或：

iteration < log₂(log₂(n)) + 1

因此将是：

ceil(log₂(log₂(n)))

次迭代。（假设 n > sqrt(2) 并从 1 开始计算迭代次数。）

Answer 3

在第j次迭代中，i是2^{2^j}，所以有 O(log log n) 次迭代。

Answer 4

Ryan 已经回答了这个问题。这只是为了解释第 j 次迭代，i 是 2^{2^j}

2         = 2^1 //iteration 0
2 * 2     = 2^2 //iteration 1
2^2 * 2^2 = 2^4 //iteration 2
2^4 * 2^4 = 2^8 //iteration 3
2^8 * 2^8 = 2^16 //iteration 4

y = 2^{2^j}

log y = 2^j

log (log y) = j

因此，总迭代次数为log (log y)

算法复杂度分析C++

Algorithm complexity analysis C++

complexity-theory

big-o

loops

time-complexity

c++11