這個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））