이 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 

때 16,

는 따라서 루프는 중지 :

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

복잡성이 LOG2는 (은 log2 (N))이다