홍라이프 계산기마스터 정리 풀이 쉽게 이해하기 — 개념과 원리
분할 정복 알고리즘의 실행 시간은 흔히 T(n) = a·T(n/b) + f(n)이라는 점화식으로 나타납니다. 크기 n인 문제를 크기 n/b인 부분 문제 a개로 나누어 재귀적으로 풀고, 나누고 합치는 데 f(n)만큼 일한다는 뜻입니다. 마스터 정리를 쓰면 재귀를 일일이 전개하지 않고도 점근적인 해를 바로 구할 수 있습니다. a, b, f(n) = nᵏ의 지수 k, 추가 로그 인수 logᵖ n의 p를 입력합니다.
계산 방법
- 임계 지수 c = log_b a = ln a ÷ ln b를 구합니다.
- k < c이면(경우 1) T(n) = Θ(n^c)입니다.
- k = c이면(경우 2) T(n) = Θ(nᵏ · log^(p+1) n)입니다.
- k > c이면(경우 3) T(n) = Θ(nᵏ · logᵖ n), 즉 Θ(f(n))입니다.
원리
재귀 트리를 그려 보면 i번째 층에는 크기 n/bⁱ인 문제가 aⁱ개 있으므로 그 층의 작업량은 aⁱ · f(n/bⁱ)입니다. 층은 약 log_b n개이고 맨 아래 잎은 a^(log_b n) = n^(log_b a)개입니다. 결국 트리의 어느 부분이 일을 가장 많이 하느냐의 문제입니다. f가 n^c보다 느리게 자라면 잎이 지배하고(경우 1), 같으면 모든 층의 비용이 비슷해 층 수 log n이 곱해지며(경우 2), 더 빠르면 뿌리의 작업이 지배합니다(경우 3). f가 다항식이면 경우 3에 필요한 정칙 조건은 자동으로 성립합니다.
예제 풀이
- 입력값: a = 2, b = 2, k = 1, p = 0이며, 병합 정렬의 T(n) = 2T(n/2) + n입니다.
- 임계 지수는 log₂ 2 = 1입니다.
- k = 1이 c = 1과 같으므로 경우 2입니다.
- T(n) = Θ(n · log^(0+1) n) = Θ(n log n)입니다.
결과 해석
알려진 알고리즘과 비교해 보면 이해가 쉽습니다. 이진 탐색(a = 1, b = 2, k = 0)은 Θ(log n), 카라추바 곱셈(a = 3, b = 2, k = 1)은 Θ(n^1.585), 슈트라센 행렬 곱셈(a = 7, b = 2, k = 2)은 Θ(n^2.807)입니다. 부분 문제의 개수 a를 줄이면 임계 지수가 낮아지므로, 더 빠른 알고리즘을 만드는 핵심이 되는 경우가 많습니다.
흔한 실수
- T(n) = T(n/3) + T(2n/3) + n처럼 부분 문제 크기가 다를 때 적용하는 경우입니다. 이때는 아크라-바지 방법이나 재귀 트리를 씁니다.
- T(n) = T(n − 1) + n처럼 n/b 꼴이 아닌 점화식에 적용하는 경우입니다.
- 경우 2에서 p에 음수를 넣는 경우입니다. p + 1 규칙은 p > −1일 때만 맞습니다.
자주 묻는 질문
답에서 로그의 밑이 중요한가요?
아닙니다. 밑을 바꾸면 상수배만 달라지므로 Θ(n log n)은 어떤 밑이든 같은 차수입니다.
f(n)이 n의 거듭제곱이 아니면 어떻게 하나요?
n^c와 다항식 수준으로 비교할 수 있으면 적용할 수 있고, 그렇지 않으면 재귀 트리나 아크라-바지 방법을 씁니다.
마스터 정리는 누가 만들었나요?
1980년 벤틀리, 하켄, 색스가 일반형을 발표했고 코멘 등의 교재를 통해 널리 알려졌습니다.
출처: J. L. Bentley, D. Haken, J. B. Saxe, "A general method for solving divide-and-conquer recurrences", SIGACT News 12(3), 1980 · T. H. Cormen 외, Introduction to Algorithms, MIT Press