마스터 정리

1. 개요

마스터 정리는 분할 정복 알고리즘의 시간 복잡도를 분석하는 데 사용되는 방법이다. T(n) = aT(n/b) + f(n) 형태의 점화식에 적용되며, 여기서 a는 재귀 호출되는 부분 문제의 수, b는 각 부분 문제의 크기가 감소하는 비율, f(n)은 문제를 분할하고 결과를 결합하는 데 드는 시간 복잡도를 나타낸다. f(n)과 logb a의 관계에 따라 세 가지 경우로 나누어 시간 복잡도를 계산하며, 경우 2는 여러 하위 경우로 확장될 수 있다. 이 정리는 이진 탐색, 병합 정렬과 같은 일반적인 알고리즘의 시간 복잡도를 분석하는 데 활용된다. 하지만 a가 상수(constant)가 아니거나, f(n)과 n^(logb a) 사이에 비다항식적 차이가 있는 경우에는 적용할 수 없다.

2. 일반적인 형태

마스터 정리는 다음과 같은 형태의 점화 관계에 적용된다.

:$T(n)\; =\; a\; \backslash ;\; T\backslash left(\backslash frac\{n\}\{b\}\backslash right)\; +\; f(n)$

여기서 $n$은 문제의 크기, $a$는 재귀적으로 호출되는 부분 문제의 수, $b$는 각 부분 문제의 크기가 감소하는 비율, $f(n)$은 문제를 분할하고 결과를 결합하는 데 드는 시간 복잡도를 나타낸다. $a$와 $b$는 $n$에 의존하지 않는 상수여야 한다.

이러한 형태의 재귀 관계는 주어진 문제를 동일한 크기의 더 작은 하위 문제로 분할하고, 하위 문제를 재귀적으로 해결한 다음, 하위 문제의 해법을 결합하여 원래 문제의 해법을 제시하는 분할 정복 알고리즘의 수행 시간을 나타낸다.

2.1. 임계 지수

마스터 정리는 문제 분할/재결합 작업 $f(n)$과 임계 지수 $c\_\{\backslash operatorname\{crit\}\}\; =\; \backslash log\_b\; a$의 관계에 따라 세 가지 경우로 나뉜다. 임계 지수는 다음과 같이 정의된다.

:$c\_\{\backslash operatorname\{crit\}\}\; =\; \backslash log\_b\; a\; =\; \backslash log(\backslash text\{하위\; 문제\; 수\})/\backslash log(\backslash text\{상대적\; 하위\; 문제\; 크기\})$

여기서 $a$는 재귀에서 하위 문제의 수, $b$는 각 재귀 호출에서 하위 문제의 크기가 감소하는 인자이다.

2.2. 세 가지 경우

마스터 정리는 분할 정복 알고리즘의 재귀 관계에 대해 점근적 타이트 바운드를 제공한다. 이 정리는 다음과 같은 형태의 재귀 관계에 적용된다.

:$T(n)\; =\; a\; \backslash ;\; T\backslash !\backslash left(\backslash frac\{n\}\{b\}\backslash right)\; +\; f(n)$

여기서 $n$은 입력 크기, $a$는 하위 문제의 수, $b$는 각 하위 문제의 크기가 감소하는 인자($b\; >\; 1$)이며, $f(n)$은 재귀의 최상위 수준에서 소요되는 시간이다. $a$와 $b$는 $n$에 의존하지 않는다.

마스터 정리는 문제 분할/재결합 작업 $f(n)$이 임계 지수 $c\_\{\backslash operatorname\{crit\}\}=\backslash log\_b\; a$와 어떻게 관련되는지에 따라 세 가지 경우로 나뉜다.

:$c\_\{\backslash operatorname\{crit\}\}\; =\; \backslash log\_b\; a\; =\; \backslash log(\backslash \#\backslash text\{하위\; 문제\})/\backslash log(\backslash text\{상대적\; 하위\; 문제\; 크기\})$

2.2.1. 경우 2의 확장

Master theorem^영어는 모든 $k$ 값에 대해 $f(n)\; =\; \backslash Theta(n^\{c\_\{\backslash operatorname\{crit\}\}\}\backslash log^\{k\}\; n)$일 때, 다음과 같이 세분화할 수 있다.

3. 예시

마스터 정리는 알고리즘의 복잡도를 분석하는 데 사용되는 방법 중 하나이다. 마스터 정리가 적용되는 몇 가지 예시는 다음과 같다.

* 경우 1: $T(n)\; =\; 8\; T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; 1000n^2$
* 경우 2: $T(n)\; =\; 2T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; 10n$
* 경우 3: $T(n)\; =\; 2\; T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; n^2$

3.1. 경우 1 예시

:$T(n)\; =\; 8\; T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; 1000n^2$

위 공식에서:

:$a\; =\; 8,\; \backslash ,\; b\; =\; 2,\; \backslash ,\; f(n)\; =\; 1000n^2$이고,
:$f(n)\; =\; O\backslash left(n^c\backslash right)$이며, 여기서 $c\; =\; 2$이다.

다음으로, Case 1 조건을 만족하는지 확인하면:
:$\backslash log\_b\; a\; =\; \backslash log\_2\; 8\; =\; 3>c$이다.

따라서 마스터 정리의 첫 번째 경우에 해당하므로:

:$T(n)\; =\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash right)\; =\; \backslash Theta\backslash left(\; n^\{3\}\; \backslash right)$

(이 결과는 점화식의 정확한 해인 $T(n)\; =\; 1001\; n^3\; -\; 1000\; n^2$에 의해 확인되며, $T(1)\; =\; 1$을 가정한다).

3.2. 경우 2 예시

$T(n)\; =\; 2T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; 10n$

위 공식에서 변수는 다음과 같은 값을 갖는다.

:$a\; =\; 2,\; \backslash ,\; b\; =\; 2,\; \backslash ,\; c\; =\; 1,\; \backslash ,\; f(n)\; =\; 10n$
:$f(n)\; =\; \backslash Theta\backslash left(n^\{c\}\; \backslash log^\{k\}\; n\backslash right)$ 여기서 $c\; =\; 1,\; k\; =\; 0$

다음으로, 경우 2 조건을 만족하는지 확인한다.

:$\backslash log\_b\; a\; =\; \backslash log\_2\; 2\; =\; 1$이므로, c와 $\backslash log\_b\; a$는 같다.

따라서 마스터 정리의 두 번째 경우를 따른다.

:$T(n)\; =\; \backslash Theta\backslash left(\; n^\{\backslash log\_b\; a\}\; \backslash log^\{k+1\}\; n\backslash right)\; =\; \backslash Theta\backslash left(\; n^\{1\}\; \backslash log^\{1\}\; n\backslash right)\; =\; \backslash Theta\backslash left(n\; \backslash log\; n\backslash right)$

따라서 주어진 점화식 $T(n)$은 $\backslash Theta(n\; \backslash log\; n)$이다.

(이 결과는 점화식의 정확한 해인 $T(n)\; =\; n\; +\; 10\; n\backslash log\_2\; n$에 의해 확인되며, $T(1)\; =\; 1$이라고 가정한다.)

3.3. 경우 3 예시

:$T(n)\; =\; 2\; T\backslash left(\backslash frac\{n\}\{2\}\backslash right)\; +\; n^2$
위 공식에서 변수는 다음과 같은 값을 갖는다.
:$a\; =\; 2,\; \backslash ,\; b\; =\; 2,\; \backslash ,\; f(n)\; =\; n^2$
:$f(n)\; =\; \backslash Omega\backslash left(n^c\backslash right)$, 여기서 $c\; =\; 2$이다.
다음으로, Case 3 조건을 만족하는지 확인한다.
:$\backslash log\_b\; a\; =\; \backslash log\_2\; 2\; =\; 1$이므로, $c\; >\; \backslash log\_b\; a$이다.
규칙성 조건도 만족한다.
:$2\; \backslash left(\backslash frac\{n^2\}\{4\}\backslash right)\; \backslash le\; k\; n^2$, $k\; =\; 1/2$를 선택한다.
따라서 마스터 정리의 세 번째 경우에서 다음과 같은 결과를 얻는다.
:$T\; \backslash left(n\; \backslash right)\; =\; \backslash Theta\backslash left(f(n)\backslash right)\; =\; \backslash Theta\; \backslash left(n^2\; \backslash right).$
주어진 점화 관계 $T(n)$은 $\backslash Theta(n^2)$이며, 이는 원래 공식의 $f(n)$과 일치한다.
(이 결과는 점화 관계의 정확한 해인 $T(n)\; =\; 2\; n^2\; -\; n$에 의해 확인되며, $T(1)\; =\; 1$이라고 가정한다.)

4. 적용 불가한 경우

다음 방정식은 마스터 정리를 사용하여 풀 수 없다.

* $T(n)\; =\; 2^nT\backslash left\; (\backslash frac\{n\}\{2\}\backslash right\; )+n^n$
*: a가 상수가 아님; 하위 문제의 수는 고정되어 있어야 함
* $T(n)\; =\; 2T\backslash left\; (\backslash frac\{n\}\{2\}\backslash right\; )+\backslash frac\{n\}\{\backslash log\; n\}$
*: $f(n)$과 $n^\{\backslash log\_b\; a\}$ 사이의 비다항식적 차이 (아래 참조; 확장 버전이 적용됨)
* $T(n)\; =\; 64T\backslash left\; (\backslash frac\{n\}\{8\}\backslash right\; )-n^2\backslash log\; n$
*: $f(n)$는 결합 시간이며 양수가 아님
* $T(n)\; =\; T\backslash left\; (\backslash frac\{n\}\{2\}\backslash right\; )+n(2-\backslash cos\; n)$
*: 사례 3이지만 정규성 위반.

위의 두 번째 허용 불가 예에서, $f(n)$과 $n^\{\backslash log\_b\; a\}$의 차이는 비율 $\backslash frac\{f(n)\}\{n^\{\backslash log\_b\; a\}\}\; =\; \backslash frac\{n\; /\; \backslash log\; n\}\{n^\{\backslash log\_2\; 2\}\}\; =\; \backslash frac\{n\}\{n\; \backslash log\; n\}\; =\; \backslash frac\{1\}\{\backslash log\; n\}$으로 표현할 수 있다. 가 임의의 상수 $\backslash epsilon\; >\; 0$에 대해 성립한다는 것은 명백하다. 따라서 차이는 다항식이 아니며 마스터 정리의 기본 형태는 적용되지 않는다. 확장된 형태(사례 2b)가 적용되어 해는 $T(n)\; =\; \backslash Theta(n\backslash log\backslash log\; n)$이 된다.

5. 일반적인 알고리즘에의 응용