점화 관계식이란?
점화 관계식(recurrence relation)은 어떤 항을 앞선 항들의 함수로 재귀적으로 정의하는 방정식입니다. 특히 알고리즘 분석에서는 재귀 함수의 실행 시간을 나타낼 때 널리 사용되며, 마스터 정리(Master Theorem)를 활용하면 점화식의 시간 복잡도를 체계적으로 구할 수 있습니다.
마스터 정리는 T(n) = aT(n/b) + f(n) 형태(a ≥ 1, b > 1)의 점화식에 적용되며, f(n)과 n^(log_b(a))의 크기를 비교하여 세 가지 경우로 답을 결정합니다.
- 경우 1: f(n) = O(n^c)이고 c < log_b(a)이면 → T(n) = Θ(n^(log_b(a)))
- 경우 2: f(n)이 n^(log_b(a))와 같은 차수이면 → T(n) = Θ(n^(log_b(a)) log n)
- 경우 3: f(n) = Ω(n^c)이고 c > log_b(a)이면 → T(n) = Θ(f(n))
이제 실제 예제를 통해 점화식을 하나씩 풀어 보겠습니다.
예제 1: T(n) = 12T(n/2) + 9n² + 2
T(n) = 12T(n/2) + 9n^2 + 2 a = 12, b = 2, f(n) = 9n^2 + 2 f(n) = O(n^c) 형태이며, 여기서 c = 2
이 점화식은 마스터 정리의 적용 조건을 만족합니다.
log_b(a) = log₂(12) ≈ 3.58 n^3.58 > n^2 이므로 경우 1(Case 1)이 적용됩니다. 따라서 T(n) = Θ(n^3.58)
예제 2: T(n) = 5T(n/2 + 23) + 5n² + 7n − 5/3
T(n) = 5T(n/2 + 23) + 5n^2 + 7n − 5/3
n이 충분히 큰 값일 때는 n과 n/2가 23보다 훨씬 크므로 상수항 23은 무시할 수 있습니다.
T(n) = 5T(n/2) + 5n^2 + 7n − 5/3 5n^2 + 7n − 5/3 ≃ O(n^2) 따라서 T(n) = 5T(n/2) + O(n^2)
이때 a = 5, b = 2이고 log₂(5) ≈ 2.32입니다. f(n)의 차수(c = 2)가 log_b(a)보다 작으므로 이 경우에도 경우 1이 적용됩니다.
따라서 T(n) = Θ(n^2.32)
마스터 정리 적용 가능 여부 판별하기
다음 점화식들이 마스터 정리의 어느 경우에 해당하는지 확인해 보겠습니다.
T(n) = 2T(n/3) + 5ⁿ
아니요. 마스터 정리를 적용하려면 f(n)이 다항 함수여야 하는데, 5ⁿ은 지수 함수이므로 해당하지 않습니다.
T(n) = 2T(n/5) + tan(n)
아니요. 탄젠트(tan)와 같은 삼각 함수는 마스터 정리의 적용 대상이 아닙니다.
T(n) = 5T(n+1) + log(n)
아니요. 로그 함수는 다항 함수 형태가 아니며, 부분 문제의 크기가 n+1로 오히려 커지므로 T(n/b) 형태도 만족하지 않습니다.
T(n) = T(n−7) + eⁿ
아니요. 지수 함수 eⁿ은 물론이고, n−7처럼 일정량을 빼는 감산형 점화식도 마스터 정리로 풀 수 없습니다.
T(n) = 9T(n/2 + 1) + 4n² − 17
네. 예제 2와 동일한 방식으로 처리할 수 있습니다. n이 충분히 크면 n/2 + 1 ≈ n/2이고 4n² − 17 = O(n²)이므로 마스터 정리를 적용할 수 있습니다.
정리
마스터 정리는 매우 유용한 도구이지만, f(n)이 다항 함수이고 부분 문제의 크기가 n/b 형태로 균등하게 나누어질 때만 적용할 수 있습니다. 지수 함수나 삼각 함수, 로그 함수가 포함되었거나 감산형으로 정의된 점화식은 반복 대입(iteration) 방법이나 재귀 트리(recursion tree) 같은 다른 기법으로 해결해야 합니다.