대입법(Substitution Method)이란?
이 글에서는 대입법을 사용하여 점화식(recurrence relation)을 푸는 방법을 살펴봅니다. 이진 탐색과 병합 정렬이라는 두 가지 대표적인 예제를 통해 개념을 더욱 명확하게 이해할 수 있습니다.
대입법은 점화식의 우변에 있는 재귀 항목에 동일한 식을 반복적으로 대입하면서 일반적인 패턴을 찾아내고, 이를 통해 알고리즘의 전체 시간 복잡도를 유도하는 방법입니다.
예제 1: 이진 탐색(Binary Search)
이진 탐색은 정렬된 배열에서 특정 원소를 찾는 기법입니다. 먼저 배열의 중앙에 찾고자 하는 원소가 있는지 확인하고, 원소가 중앙에 있다면 알고리즘은 종료됩니다. 그렇지 않다면 배열의 왼쪽 절반 또는 오른쪽 절반 중 해당하는 부분 배열을 대상으로 같은 과정을 반복합니다. 즉, 각 단계마다 탐색 범위가 절반(n/2)씩 줄어듭니다.
이진 탐색 알고리즘의 실행 시간을 T(n)이라 하고, 기저 조건(base case)은 상수 시간 O(1)이 걸린다고 가정하면 점화식은 다음과 같이 표현할 수 있습니다.
$$T(n)=\begin{cases}T(1) & for\:n \leq 1\\T(\frac{n}{2})+c & for\:n > 1\end{cases}$$
점화식 풀이
각 단계마다 공식을 반복해서 대입하여 결과를 구해 보겠습니다.
$$T(n)=T(\frac{n}{2})+c$$
T(n/2)를 대입하면,
$$T(n)=(T(\frac{n}{4})+c)+c$$
$$T(n)=T(\frac{n}{4})+2c$$
$$T(n)=T(\frac{n}{8})+3c$$
$$T(n)=T(\frac{n}{2^{k}})+kc$$
n/2k가 1에 도달하면 2k = n이 되므로, k = log2n입니다. 이를 대입하면 T(n) = T(1) + c·log2n이 되며, 상수항을 무시하면 다음과 같은 결론을 얻습니다.
T(n)의 시간 복잡도 = ϴ(log n)
예제 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}$$
점화식 풀이
마찬가지로 각 단계마다 공식을 반복해서 대입해 보겠습니다.
$$T(n)=2T(\frac{n}{2})+cn$$
T(n/2)를 대입하면,
$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2})+cn$$
$$T(n)=4T(\frac{n}{4})+2cn$$
$$T(n)=8T(\frac{n}{8})+3cn$$
$$T(n)=2^{k}T(\frac{n}{2^{k}})+kcn$$
n/2k가 1에 도달하면 2k = n이 되므로 k = log2n입니다. 이를 대입하면 T(n)은 다음과 같이 됩니다.
𝑇(𝑛) = 𝑛𝑇(1) + 𝑐𝑛 log2𝑛
여기서 nT(1)은 선형 항이므로 지배적인 항은 cn log₂n이며, 최종적으로 다음과 같은 결론을 얻습니다.
시간 복잡도 = θ(n log n)
정리
대입법은 점화식을 반복적으로 전개하여 패턴을 발견하고, 재귀가 종료되는 시점(k = log₂n)을 대입함으로써 알고리즘의 시간 복잡도를 구하는 강력한 기법입니다. 이진 탐색은 매 단계 문제의 크기가 절반으로 줄어들어 ϴ(log n), 병합 정렬은 분할 후 선형 시간의 병합 작업이 추가되어 θ(n log n)의 복잡도를 갖습니다.