C++ 시간 복잡도 완벽 분석: 조화급수와 팩토리얼 로그로 이해하기

시간 복잡도(Time Complexity)란 알고리즘이 평균적인 경우(average case)를 수행하는 데 필요한 시간을 의미합니다. 알고리즘의 효율성을 평가하는 핵심 지표이기 때문에, 코딩 테스트나 기술 면접에서 자주 다뤄지는 주제입니다.

이번 글에서는 겉보기에는 단순해 보이지만 계산 과정이 흥미로운 두 가지 기본 함수를 통해 시간 복잡도를 직접 구해 보겠습니다.

예제 1: 배수만큼 건너뛰는 내부 반복문

void counter(int n){
    for(int i = 0 ; i < n ; i++){
        for(int j = 1 ; j < n ; j += i){
            cout << i << " " << j;
        }
        cout << endl;
    }
}

위 코드의 핵심은 내부 반복문입니다. 내부 반복문은 외부 변수 i의 값만큼 j가 증가하므로, 각 i에 대해 약 n/i번 실행됩니다. 즉, 첫 번째 반복(i = 1)에서는 n번, 마지막 반복(i = n)에서는 1번 실행됩니다.

이를 모두 더하면 전체 실행 횟수는 다음과 같습니다.

n/1 + n/2 + n/3 + … + n/n
= n × (1/1 + 1/2 + 1/3 + … + 1/n)

여기서 괄호 안의 식 (1/1 + 1/2 + 1/3 + … + 1/n)은 유명한 조화급수(Harmonic Series)로, 그 값은 O(log n)에 해당합니다. 따라서 전체 시간 복잡도는 다음과 같이 결론 지을 수 있습니다.

시간 복잡도: O(n log n)

예제 2: 로그 횟수만큼 도는 내부 반복문

void counter(int n){
    int i, j;
    for(int i = 1 ; i <= n ; i++){
        for(j = 1 ; j <= log(i) ; j++){
            cout << i << " " << j;
        }
    }
}

이번에는 내부 반복문이 log(i)번 실행됩니다. 외부 반복문이 i를 1부터 n까지 순회하므로, 총 실행 횟수는 각 단계의 로그 값을 모두 더한 형태가 됩니다.

O(log 1) + O(log 2) + O(log 3) + … + O(log n)
= O(log(1 × 2 × 3 × … × n))
= O(log n!)

로그의 성질에 의해 각 항의 합은 곱셈의 로그로 바꿀 수 있으며, 결과적으로 O(log n!)이 됩니다. 참고로 스털링 근사(Stirling's Approximation)에 따르면 log n! ≈ n log n이므로, 이 코드 역시 사실상 O(n log n) 수준의 복잡도를 가진다고 볼 수 있습니다.

정리

두 예제 모두 단순한 이중 반복문처럼 보이지만, 내부 반복문의 증가 방식(배수 증가 vs 로그 횟수)에 따라 분석 방법이 달라집니다. 조화급수와 로그의 누적 합 같은 수학적 개념을 활용하면 복잡해 보이는 반복문도 체계적으로 분석할 수 있습니다. 이러한 접근 방식은 알고리즘 최적화와 성능 예측에 큰 도움이 됩니다.