알고리즘 시간 복잡도 계산하기: 효율성을 높이자!

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간을 수학적으로 표현한 것으로, 입력의 크기에 따라 실행 시간이 어떻게 증가하는지 나타낸다. 이 시간 복잡도 계산은 효율적인 알고리즘을 설계하고, 문제의 제약 조건에 맞게 최적의 접근을 찾기 위한 핵심적인 과정이다.

이번 글에서는 시간 복잡도를 계산하는 기본 개념과 방법을 설명하고자 한다.

---

시간 복잡도를 왜 계산해야 할까?

시간 복잡도를 계산하는 것은 알고리즘의 효율성을 예측하기 위해 중요하다. 시간 제한이 있는 프로그래밍 문제에서, 알고리즘이 제한 시간 내에 문제를 해결할 수 있을지 판단하려면 시간 복잡도를 알고 있어야 한다.
시간 복잡도를 표현하기 위해 O 표기법(Big-O Notation), Θ 표기법(Theta Notation), 그리고 Ω 표기법(Omega Notation)이 존재한다. 각 표기법은 입력 크기 N이 커짐에 따라 알고리즘의 시간 또는 공간 복잡도가 어떻게 증가하는지를 나타낸다.

$O(), Θ(), Ω()$ 표기법이란?

1. O 표기법 (Big-O Notation)

O 표기법은 알고리즘의 최악의 경우를 기준으로 시간 복잡도나 공간 복잡도를 표현한다. 즉, 입력이 최대치로 주어졌을 때 성능이 어떻게 되는지를 평가하며, 성능 분석에서 가장 일반적으로 사용된다.

예를 들어, 이중 반복문을 사용하는 알고리즘이 있다고 하자. 이 경우 시간 복잡도는 입력 크기 N에 대해 $O(N^2)$가 된다. 이는 N이 커질수록 알고리즘의 실행 시간이 $N^2$에 비례해 증가한다는 것을 의미한다.

2. Θ 표기법 (Theta Notation)

Θ 표기법은 알고리즘의 평균적인 시간 복잡도를 나타내며, 최악과 최선이 동일한 경우에 주로 사용한다. Θ 표기법은 알고리즘이 최선의 경우와 최악의 경우가 같은 비율로 증가할 때 적용할 수 있다. 예를 들어, 배열의 모든 요소를 한 번씩 방문하는 단순 반복문의 시간 복잡도는 $Θ(N)$이다.

• 예: 배열의 모든 요소를 순회하는 경우 시간 복잡도는 $O(N)$이면서 $Θ(N)$이다.

3. Ω 표기법 (Omega Notation)

Ω 표기법은 최선의 경우에 대한 시간 복잡도를 나타낸다. 알고리즘이 최대한 빠르게 동작할 때의 실행 시간을 표현하며, 예외적으로 입력 조건이 가장 유리할 때의 성능을 평가할 수 있다.

예를 들어, 정렬되지 않은 배열에서 최댓값을 찾는 알고리즘은 최악의 경우 $O(N)$의 시간 복잡도를 가지지만, 최선의 경우에는 첫 번째 요소가 최대일 때 바로 답을 찾으므로 $Ω(1)$이 될 수 있다.

O(), Θ(), Ω() 표기법 요약

표기법	설명	사용 예시
O()	최악의 경우 시간 복잡도	대부분의 성능 평가 시 사용
Θ()	평균적인 시간 복잡도	최선과 최악이 동일한 경우 사용
Ω()	최선의 경우 시간 복잡도	최선의 경우를 따로 평가할 때 사용

이 중에서도 실제 프로그래밍 문제 해결과 알고리즘 성능 평가에서 가장 많이 사용되는 것은 O 표기법(Big-O Notation)이다.

실제 상황에서 알고리즘이 최악의 경우에도 성능을 보장하는지가 매우 중요하기 때문이다.

[!NOTE]

대부분의 문제 풀이 환경에서는 입력이 최대 크기로 주어졌을 때의 성능을 고려해 채점이 이루어지므로, 최악의 경우를 평가하는 O 표기법을 따르는 것이 유리하다.

---

• 예를 들어, 입력 크기 N이 1,000,000이라면, $O(N^2)$ 알고리즘은 시간 초과가 발생할 가능성이 크다. 반면 $O(N log N)$이나 $O(N)$ 알고리즘이라면 제한 시간 내에 해결될 가능성이 높다.

시간 복잡도 그래프

시간 복잡도를 한눈에 이해하기 위해 시각 자료를 활용하는 것이 좋다. 다음과 같은 시간 복잡도의 그래프를 통해, 각 시간 복잡도가 N의 증가에 따라 어떻게 변하는지 시각적으로 확인할 수 있다.

---

시간 복잡도 계산 기본 원칙

시간 복잡도를 계산할 때는 다음 원칙을 따른다:

1. 상수와 낮은 차수는 무시: 시간 복잡도는 대체로 입력 크기 N이 충분히 큰 상황을 가정하므로, 상수는 생략하고 가장 큰 차수에 따라 복잡도를 표기한다.
   • 예: $O(3N + 2)$ → $O(N)$, $O(N^2 + 5N + 10)$ → $O(N^2)$
2. 가장 큰 차수에 따라 결정: 입력이 커질수록 실행 시간에 가장 큰 영향을 미치는 연산만 고려한다.
   • 예: $O(N + N^2)$ → $O(N^2)$
3. 중첩된 반복문: 반복문이 중첩되면 차수가 더 높아진다. 예를 들어, 이중 반복문은 $O(N^2)$가 된다.
4. 독립적 반복문의 합: 서로 독립적으로 실행되는 반복문이 있을 경우, 각각의 시간 복잡도를 더한다.
   • 예: 반복문 $O(N)$이 두 번 등장하면 $O(2N) → O(N)$

---

주요 시간 복잡도 예제와 계산법

$O(1)$ - 상수 시간

입력 크기에 상관없이 일정한 시간이 걸리는 경우로, 보통 단일 연산에 해당한다.

int x = 10;
cout << x;

• 위 코드는 연산이 하나뿐이므로 $O(1)$이다.

$O(log N)$ - 로그 시간

$O(log N)$은 반으로 줄이는 연산에서 자주 등장하며, 대표적인 예로 이진 탐색이 있다. 로그 시간은 N의 증가에 비해 매우 천천히 증가한다.

int binarySearch(int arr[], int left, int right, int x) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

• 이진 탐색은 매번 탐색 범위를 절반으로 줄이므로 O(log N)이 된다.

$O(N)$ - 선형 시간

$O(N)$은 입력 크기 N에 비례해 실행 시간이 증가하는 경우다. 배열 전체를 한 번 순회하는 경우가 대표적이다.

int sumArray(int arr[], int N) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += arr[i];
    }
    return sum;
}

• 위 코드는 배열을 한 번 순회하며 합산하므로 $O(N)$이다.

$O(N log N)$ - 선형 로그 시간

$O(N log N)$은 정렬 알고리즘에서 자주 등장하는 시간 복잡도로, N개의 요소를 반복적으로 나누어 정렬하는 데 걸리는 시간이다.

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

• 병합 정렬(merge sort)은 배열을 반으로 나누며 재귀적으로 정렬하고 합친다. 이 과정에서 O(N log N)이 된다.

$O(N^2)$ - 이차 시간

$O(N^2)$은 이중 반복문에서 발생하며, N이 증가함에 따라 실행 시간이 제곱으로 증가한다. 예를 들어, 배열 내 두 요소의 모든 쌍을 비교하는 알고리즘이 있다.

void printAllPairs(int arr[], int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << arr[i] << ", " << arr[j] << endl;
        }
    }
}

• 위 코드는 이중 반복문이기 때문에 $O(N^2)$의 시간 복잡도를 가진다.

$O(2^N)$ - 지수 시간

$O(2^N)$은 입력 크기에 따라 지수적으로 증가하는 시간 복잡도로, 재귀적 문제에서 자주 발생한다. 예를 들어 피보나치 수열을 재귀적으로 계산하는 경우가 있다.

int fibonacci(int N) {
    if (N <= 1) return N;
    return fibonacci(N - 1) + fibonacci(N - 2);
}

• 피보나치 수열을 재귀적으로 계산하면 중복 호출이 발생해 O(2^N)이 된다.

$O(N!)$ - 팩토리얼 시간

$O(N!)$은 모든 가능한 순열을 생성해야 하는 경우 발생하며, N의 크기에 따라 실행 시간이 폭발적으로 증가한다. 예를 들어, N개의 숫자에 대해 모든 순열을 출력하는 문제다.

void permute(vector<int>& nums, int l, int r) {
    if (l == r) {
        for (int num : nums) cout << num << " ";
        cout << endl;
    } else {
        for (int i = l; i <= r; i++) {
            swap(nums[l], nums[i]);
            permute(nums, l + 1, r);
            swap(nums[l], nums[i]);
        }
    }
}

• 위 코드는 순열을 생성하며 $O(N!)$의 시간 복잡도를 가진다.

---

시간 복잡도 계산 연습 예제

예제 1: 최대 공약수(GCD) 계산

유클리드 알고리즘을 사용한 최대 공약수(GCD) 계산은 $O(log N)$의 시간 복잡도를 가진다. 두 수를 a, b라 할 때, 매번 b의 값이 절반 이하로 줄어들기 때문이다.

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

예제 2: 특정 합을 찾는 부분 배열

부분 합이 K인 배열의 구간을 찾는 문제는 두 가지 방법이 있다.

1. 이중 반복문 사용: 모든 구간을 탐색하므로 $O(N^2)$의 시간 복잡도가 발생한다.
2. 누적 합과 해시맵 사용: 해시맵을 활용해 $O(N)$으로 해결할 수 있다.

이처럼 문제를 풀 수 있는 다양한 방법을 찾아 시간 복잡도를 줄이는 연습이 필요하다.

---

마무리: 시간 복잡도 계산을 통해 효율적인 알고리즘 설계하기

시간 복잡도를 계산하는 것은 효율적인 코드 작성을 위한 중요한 과정이다. 위에서 설명한 시간 복잡도 계산 원칙을 기억하고, 다양한 알고리즘과 예제를 통해 실제 문제에 적용해보자. 꾸준히 연습하며 최적의 알고리즘을 선택할 수 있는 능력을 기르면, 더 복잡한 문제도 자신 있게 해결할 수 있을 것이다.