중첩 루프의 시간 복잡도

Question

다음 알고리즘에서 최악의 시간 복잡도를 찾으려고합니다.

for (i = N*N; i>1; i = i /2){ 
    for (j = 0; j < i; j++){ 
    counter++; 
    } 
} 

나는 내부 루프가 로그 방식으로 실행할 것을 알아 내기 위해 관리 (거꾸로 생각,하지만 난 나던 문제가 있다고 생각)하지만 메신저 외부 루프에 접근하는 방법을 정말 확실.

Answer 1

@ClintPowell이 지적했듯이, 내부 루프는 O(i)입니다. 트릭은 i에 대한 다양한 값을 더하는 것입니다.

외부 루프가 i=1; i<=K; i=i*2 (사용자가 지적했듯이 순서는 중요하지 않음)이라고 가정하고 K으로 해결하십시오. 그런 다음 K을 N*N으로 대체하고 필요에 따라 단순화하십시오.

Answer 2

물론 외부 루프는 log n 번 실행되고 내부 루프는 i 번 실행됩니다. k = log n이라면 1에서 k까지의 i의 합은 k (k + 1)/2가 될 것입니다. 이것은 O (log n)^2입니다. 희망이 도움이됩니다.