시간 복잡도 (중첩 루프)

Question

어떻게이 시간 복잡성을 계산합니까?

int count=0; 

for (int i=1 ; i < n; i*=4) 

    for (int j=1;j<=n;j++) 

       count++; 

Answer 1

TL; DR은 : 게시 된 코드의 복잡성은 다음과 같습니다

O(nlogn)가의 안쪽에서 바깥을 분석해 보겠습니다. 내부 루프는 i의 각 값에 대해 정확히 n 번 반복됩니다.

외부 루프는 반복하고 i < n 및 i은 매번 4을 곱합니다. 즉, 첫 번째 반복 후 i=1을 입력 한 다음 i=4, i=16, i=64, ....을 입력하고 k'th을 입력 한 다음 i = 4^(k-1)을 입력합니다.

이

i >= n 
4^(k-1) >= n 
log_4(4^(k-1)) >= log_4(n) 
k-1 >= log_4(n). 

이 외부 루프는 log_4(n) + 1를 반복 의미 :이 의미
, 당신은 때 중지합니다. 모두 함께 합산

당신에게 줄의 코드 당신의 부부를 포맷하는 시간을 적어도 O(nlogn)