마스터 정리 (Master Theorem)
쉽게 풀면
분할정복 알고리즘의 실행 시간은 보통 "문제를 몇 조각으로 나누는지(a)", "조각 하나의 크기가 얼마나 줄어드는지(b)", "나누고 합치는 데 드는 추가 비용(f(n))" 세 가지로 정해지는 점화식으로 표현됩니다. 이 점화식을 매번 손으로 풀어내는 대신, 마스터 정리는 마치 완성된 공식표에 숫자만 대입하면 답이 나오는 것처럼 세 가지 조건 중 어디에 해당하는지만 확인하면 최종 시간복잡도를 바로 알려줍니다.
왜 중요한가
마스터 정리는 정렬, 탐색, 행렬 곱셈 등 재귀적으로 구성된 수많은 알고리즘의 성능을 빠르게 비교할 수 있게 해주기 때문에 알고리즘 설계 및 복잡도 분석 논문에서 표준 도구로 쓰입니다. 새로운 분할정복 알고리즘을 제안할 때 그 효율성을 기존 알고리즘과 비교하려면 점화식으로부터 시간복잡도를 유도하는 과정이 필수적인데, 마스터 정리는 이 과정을 간결하고 일관된 방식으로 처리할 수 있게 해줍니다. 이 때문에 자료구조, 병렬 알고리즘, 대규모 데이터 처리 알고리즘을 다루는 논문에서도 복잡도 증명의 표준 절차로 자주 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 알고리즘이 재귀적으로 문제를 절반씩 나누어 풀되 합치는 과정에 선형 시간이 드는 구조임을 밝히고, 그 점화식에 마스터 정리를 적용해 전체 실행 시간을 도출했다는 뜻입니다. 알고리즘 설계 및 복잡도 분석을 다루는 논문에서 흔히 볼 수 있습니다.
슈트라센 알고리즘류의 행렬 연산 최적화 연구에서도 하위 문제의 개수와 크기를 점화식으로 표현한 뒤 마스터 정리로 전체 복잡도를 정리하는 방식이 흔히 쓰인다.
조금 더 깊게 보면
마스터 정리는 점화식 T(n) = aT(n/b) + f(n)에서 f(n)이 n^(log_b a)와 비교해 더 작은지, 같은지, 더 큰지에 따라 세 가지 경우로 나누어 결과를 결정합니다. 다만 f(n)이 규칙성 조건(regularity condition)을 만족하지 못하거나 다항식 차수로 비교할 수 없는 형태(예: 로그 곱 형태)일 경우에는 표준 마스터 정리로 답을 낼 수 없어, 이런 경계 사례를 다루기 위해 아카라-바지라니(Akra-Bazzi) 방법 같은 더 일반화된 정리가 쓰이기도 합니다. 하위 문제 크기가 균등하지 않은 점화식 역시 마스터 정리의 적용 범위를 벗어나므로 재귀 트리 방법 등으로 별도 분석이 필요합니다.
주의할 점
마스터 정리는 모든 점화식에 적용할 수 있는 만능 공식이 아닙니다. 하위 문제의 크기가 균등하게 줄어들지 않거나 f(n) 항이 정해진 조건 범위를 벗어나면 마스터 정리로는 답을 구할 수 없고, 점화식을 다른 방식(대입법, 재귀 트리 등)으로 직접 풀어야 합니다.