j <= i 인 중첩 for 루프의 시간 복잡도

Question

과제에 대해이 질문을했습니다.

for(int i=1; i<=n; i=2*i){ 
    for(int j=1; j<=i; i=2*j){ 
     stuff 
    } 
} 

내가 i와 j가 2 배만큼 증가되면서 복잡성 LOG2의 라인을 따라 무언가 것이라고 이해 중첩 루프의 시간 복잡도를 결정 (N) *은 log2 (N) 그러나 내부 루프가 i가 아닌 n을 실행하면 완전히 손실됩니다.

중첩 루프의 복잡성과 해결 방법에 대한 단계별 설명이 필요합니다.

Answer 1

내부 루프는 번 (로그 기준 2)으로 실행됩니다.

외부 루프를 추가하면 i = 1, 2, 4, ... n에 대해 위의 내용을 합산하십시오.

그래서 :이다 (log(1) + 1) + (log(2) + 1) + (log(4) + 1) + ... + (log(n) + 1)

: (log(n) + 1) * (log(n) + 2)/2 = (log(n)*log(n) + 3log(n) + 2)/2 = O(log(n) * log(n))

Answer 2

는 N의 가정하자 = 예를 들어 16, 그래서 값 i = 1, 2, 4, 8, 16을 갖 1 + 2 + 3 + ... + log(n)

산술 시리즈의 합을 사용하는 것이다.

So : i는 기본적으로 log (n), 즉 log (16), 즉 5 번의 반복으로 값을 취합니다.

이제 j의 값은 log(1) + log(2) + log(4) + log(8) + log(16)입니다. 기본적으로 각 반복에서 log (i)와 같습니다.

위의 두 문장에서 얻은 값을 결합하여 위의 코드의 시간 복잡도가 O(log(n) * log(i))이라고 말할 수 있습니다.

이것은 코드에 대한 나의 이해입니다.