C++ 시간 복잡도 분석 연습 문제: 예제 코드로 배우는 빅오(Big-O) 표기법

시간 복잡도(Time Complexity)란 알고리즘이 작업을 완료하기까지 걸리는 시간을 의미합니다. 알고리즘의 효율성을 나타내는 핵심 지표이며, 여러 알고리즘을 비교 분석할 때 중요하게 활용됩니다. 일반적으로 시간 복잡도가 낮은 알고리즘일수록 더 효율적이라고 할 수 있습니다.

예제 1

다음 코드의 시간 복잡도를 구해 보세요.

for(i= 0 ; i < n; i++){
    cout<< i << " " ;
    i++;
}

루프의 최대 반복 기준값은 n이지만, for 문 내부에서 i가 한 번에 두 번씩 증가하므로 실제 반복 횟수는 절반으로 줄어듭니다. 따라서 시간 복잡도는 O(n/2)이며, 상수 인자는 무시되므로 O(n)과 동일합니다.

예제 2

다음 코드의 시간 복잡도를 구해 보세요.

for(i= 0 ; i < n; i++){
    for(j = 0; j<n ;j++){
        cout<< i << " ";
    }
}

내부 루프와 외부 루프 모두 n번씩 실행됩니다. 즉, i 값 하나당 내부 루프가 n번 돌고, i가 n개의 값을 가지므로 전체 반복 횟수는 n × n = n²번이 됩니다. 따라서 시간 복잡도는 O(n²)입니다.

예제 3

다음 코드의 시간 복잡도를 구해 보세요.

int i = n;
while(i){
    cout << i << " ";
    i = i/2;
}

이 경우 매 반복마다 i의 값이 이전 값의 절반이 됩니다. 수열은 n, n/2, n/4, …처럼 줄어들며, 총 반복 횟수는 log₂n에 비례합니다. 따라서 시간 복잡도는 O(log n)입니다.

예제 4

다음 코드의 시간 복잡도를 구해 보세요.

if(i > j ){
    j>23 ? cout<<j : cout<<i;
}

코드에는 if 문과 삼항 연산자, 두 개의 조건문이 있습니다. 각 조건문의 시간 복잡도는 O(1)이고, 두 개를 합쳐도 O(2)이지만 상수는 무시되므로 결국 O(1), 즉 상수 시간(constant time)입니다.

예제 5

다음 코드의 시간 복잡도를 구해 보세요.

for(i= 0; i < n; i++){
    for(j = 1; j < n; j = j*2){
        cout << i << " ";
    }
}

내부 루프는 j가 매번 2배씩 증가하므로 log n번 실행되고, 외부 루프는 n번 실행됩니다. i 값 하나당 내부 루프가 log n번 돌고, i가 n개의 값을 가지므로 전체 반복 횟수는 n × log n번입니다. 따라서 시간 복잡도는 O(n log n)입니다.

핵심 패턴 정리