중첩 루프의 시간 복잡도

Question

중첩 for 루프가 있습니다. 시간 복잡성은 nlg (n)입니다.

int sum = 0; 
for(int k = 1; k < n; k*=2){ 
    for(int i = 1; i < n; i++){ 
      sum++; 
    } 
} 

내 생각은 다음과 같습니다.

1. 외부 for 루프 : k은 1, 2, 4, 8, ...의 값을 취합니다. 따라서 lg (n) 반복이 소요됩니다.
2. 내부 for 루프 : i은 n 반복을 취합니다.

따라서 전체적인 작업은 nlg (n)이됩니다.

맞습니까?

Answer 1

예, 제안한 성장 순서가 정확합니다. 다음과 같이 표시 할 수 있습니다.