마스터 정리

우리는 재귀 함수의 시간 복잡도를 구하는 것이 쉽지 않다는 것을 알고 있습니다. 팩토리얼이나 병합 정렬같은 재귀 함수는 직관적으로 시간 복잡도를 알 수 있지만 쉬트라센 행렬 곱셈같은 $T(n)=7\times T({n\over 2}) + 18\times({n\over2})^2$인 함수의 시간 복잡도는 알기 힘듭니다. 이런 복잡한 재귀 함수의 시간 복잡도를 구하기 쉽도록 누군가가 공식화 했습니다. 그 공식은 이렇습니다.
어떤 알고리즘의 시간 복잡도 함수 $T(n)$이 다음과 같은 형태일 때,

• $T(n) = a\times T({n\over b}) + c\times n^k$,
• 여기서 $a, b, c, k$는 상수이고, $a, c > 0, b \ge 2, k \ge 0$.

이 함수 $T(n)의 시간 복잡도 클래스는 다음과 같다.

$T(n)\in\Theta(n^k)$, if $a < b^k$
$T(n)\in\Theta(n^k\log_2n)$, if $a = b^k$
$T(n)\in\Theta(n^{log_ba})$, if $a > b^k$

이것을 마스터 정리라고 부릅니다. 증명은 매우 힘드니 넘어가겠습니다.

참조: "알고리즘 복잡도 뽀개기: 2. 재귀 함수와 마스터 정리", 주니온 TV 아무거나연구소, 2021년 11월 27일 접속, https://www.youtube.com/watch?v=-bm0-k7UeV8