알고리즘을 분석하다 보면 점화식(recurrence relation)이라는 수학적 관계식을 자주 만나게 됩니다. 점화식이란 표현식 안에 동일한 함수가 다시 등장하는 관계식으로, 주로 재귀 알고리즘이나 분할 정복(Divide and Conquer) 알고리즘의 시간 복잡도를 분석할 때 나타납니다.
점화식이란 무엇인가?
점화식은 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘의 실행 시간을 수학적으로 표현한 것입니다. 함수 T(n)이 자기 자신을 더 작은 입력 크기에 대해 호출하는 형태로 표현되기 때문에, 재귀적 구조를 가진 알고리즘의 성능을 정확히 예측할 수 있게 해줍니다.
예제 1: 이진 탐색(Binary Search)의 점화식
첫 번째 예제로 이진 탐색 기법을 살펴보겠습니다. 이진 탐색은 배열의 중간 위치에 찾고자 하는 원소가 있는지 확인합니다. 원소가 중간에 있다면 알고리즘이 종료되고, 그렇지 않다면 실제 배열에서 왼쪽 또는 오른쪽 하위 배열을 반복적으로 탐색합니다.
이 과정에서 매 단계마다 배열의 크기는 절반(n/2)씩 줄어듭니다. 이진 탐색 알고리즘의 실행 시간을 T(n)이라 하고, 기저 조건(base case) 처리에는 O(1)의 상수 시간 c가 걸린다고 하면, 점화식은 다음과 같이 표현됩니다.
$$T(n)=\begin{cases}T(1) & for\:n \leq 1\\T(|\frac{n}{2}\rvert)+c & for\:n > 1\end{cases}$$
즉, n이 1 이하일 때는 상수 시간이 걸리고, n이 1보다 클 때는 절반 크기의 하위 문제를 해결하는 시간에 상수 시간을 더한 값이 전체 실행 시간이 됩니다.
예제 2: 병합 정렬(Merge Sort)의 점화식
다음 예제는 병합 정렬입니다. 병합 정렬은 리스트를 두 부분으로 나누고, 리스트의 크기가 1이 될 때까지 이 과정을 반복합니다. 이후 각 부분을 정렬된 순서로 병합하는데, 이 병합 단계는 O(n)의 시간이 소요됩니다.
병합 정렬 알고리즘의 실행 시간을 T(n)이라 하면, 리스트를 두 개의 절반으로 나누어 각각에 대해 동일한 작업을 수행하므로 각각 T(n/2)의 시간이 걸립니다. 따라서 점화식은 다음과 같습니다.
$$T(n)=\begin{cases}T(1) & for\:n = 1\\2T(\frac{n}{2})+cn & for\:n > 1\end{cases}$$
여기서 cn 항은 병합 단계에서 입력 크기 n에 비례하는 시간이 추가로 필요함을 의미합니다. 이 점화식을 풀면 병합 정렬의 시간 복잡도가 O(n log n)임을 유도할 수 있습니다.
점화식을 푸는 방법
이렇게 유도한 점화식은 다양한 방법으로 해결할 수 있습니다.
1. 대입법(Substitution Method): 답을 추측한 후 수학적 귀납법을 사용하여 그 추측이 올바름을 증명하는 방법입니다.
2. 재귀 트리 방법(Recursion Tree Method): 재귀 호출 구조를 트리 형태로 그려 각 레벨의 비용을 계산하고 전체 비용을 합산하는 직관적인 방법입니다.
3. 마스터 정리(Master Method): T(n) = aT(n/b) + f(n) 형태의 특수한 점화식을 표만으로 빠르게 해결할 수 있는 강력한 도구입니다.
점화식을 제대로 이해하고 활용하면 재귀 및 분할 정복 알고리즘의 성능을 체계적으로 분석할 수 있으며, 더 효율적인 알고리즘을 설계하는 데 큰 도움이 됩니다.