这个while循环的时间复杂度？

Question

这个循环的时间复杂度是多少？

j=2 
while(j <= n) 
{ 
    //body of the loop is Θ(1) 
    j=j^2 
} 

Answer 1

您有

j = 2 

并且每个循环： 当J = J^2

的模式是：

2  = 2^(2^0) 
2*2 = 2^(2^1) 
4*4 = 2^(2^2) 
16*16 = 2^(2^3) 

哪些可以被看作是：

2^(2^k) with k being the number of iteration 

时因此循环停止：

2^(2^k) >= n 
log2(2^(2^k)) >= log2(n) 
2^k >= log2(n) 
log2(2^k) >= log2(n) 
k >= log2(log2(n)) 

复杂度为log 2（LOG 2（N））