마스터 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 일반적인 형태
- 2.1. 임계 지수
- 2.2. 세 가지 경우
  - 2.2.1. 경우 2의 확장
3. 예시
4. 적용 불가한 경우
5. 일반적인 알고리즘에의 응용
참조

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. 일반적인 형태

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

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

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

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

2. 1. 임계 지수

마스터 정리는 문제 분할/재결합 작업

f(n)

과 임계 지수

c_{\operatorname{crit}} = \log_b a

의 관계에 따라 세 가지 경우로 나뉜다. 임계 지수는 다음과 같이 정의된다.

:

c_{\operatorname{crit}} = \log_b a = \log(\text{하위 문제 수})/\log(\text{상대적 하위 문제 크기})

여기서

a

는 재귀에서 하위 문제의 수,

b

는 각 재귀 호출에서 하위 문제의 크기가 감소하는 인자이다.

경우	설명	$c_{\operatorname{crit}}$ ( $\log_b a$ )와 관련된 $f(n)$ 에 대한 조건	마스터 정리 바운드	표기 예시
1	문제 분할/재결합 작업은 하위 문제에 의해 지배된다. (재귀 트리는 리프가 많다.)	$f(n) = O(n^{c})$ 이고 $c 일 때 (더 작은 지수 다항식에 의해 상한)$	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)$ (분할 항은 나타나지 않으며, 재귀 트리 구조가 지배한다.)	$b=a^2$ 이고 $f(n) = O(n^{1/2-\epsilon})$ 이면, $T(n) = \Theta(n^{1/2})$ 이다.
2	문제 분할/재결합 작업은 하위 문제와 유사하다.	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 $k \ge 0$ 일 때 (임계 지수 다항식에 의해 범위가 지정되며, 0개 이상의 선택적 $\log$ 가 곱해짐)	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)$ (바운드는 분할 항이며, 여기서 로그는 단일 지수로 증가한다.)
3	문제 분할/재결합 작업은 하위 문제를 지배한다. (재귀 트리는 루트가 많다.)	$f(n) = \Omega(n^{c})$ 이고 $c>c_{\operatorname{crit}}$ 일 때 (더 큰 지수 다항식에 의해 하한)		$b=a^2$ 이고 $f(n) = \Omega(n^{1/2+\epsilon})$ 이고 규칙성 조건이 참이면, $T(n) = \Theta(f(n))$ 이다.

경우 2의 유용한 확장으로 모든 $k$ 값을 처리한다.

경우	$c_{\operatorname{crit}}$ ( $\log_b a$ )와 관련된 $f(n)$ 에 대한 조건	마스터 정리 바운드	표기 예시
2a	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 임의의 $k > -1$ 일 때	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)$ (바운드는 분할 항이며, 여기서 로그는 단일 지수로 증가한다.)	$b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log^{1/2} n)$ 이면, $T(n) = \Theta(n^{1/2} \log^{1/2} n)$ 이다.
2b	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 $k = -1$ 일 때	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log \log n \right)$ (바운드는 분할 항이며, 여기서 로그 역수는 반복 로그로 대체된다.)	$b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log n)$ 이면, $T(n) = \Theta(n^{1/2} \log \log n)$ 이다.
2c	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 임의의 $k < -1$ 일 때	$T(n)= \Theta\left( n^{c_{\operatornameoperatorname{crit}}} \right)$ (바운드는 분할 항이며, 여기서 로그는 사라진다.)	$b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log^2 n)$ 이면, $T(n) = \Theta(n^{1/2})$ 이다.

2. 2. 세 가지 경우

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

:

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

여기서

n

은 입력 크기,

a

는 하위 문제의 수,

b

는 각 하위 문제의 크기가 감소하는 인자(

b > 1

)이며,

f(n)

은 재귀의 최상위 수준에서 소요되는 시간이다.

a

와

b

는

n

에 의존하지 않는다.

마스터 정리는 문제 분할/재결합 작업

f(n)

이 ''임계 지수''

c_{\operatorname{crit}}=\log_b a

와 어떻게 관련되는지에 따라 세 가지 경우로 나뉜다.

:

c_{\operatorname{crit}} = \log_b a = \log(\#\text{하위 문제})/\log(\text{상대적 하위 문제 크기})

경우	설명	$c_{\operatorname{crit}}$ , 즉 $\log_b a$ 와 관련된 $f(n)$ 에 대한 조건	마스터 정리 바운드	표기 예시
1	문제 분할/재결합 작업이 하위 문제에 의해 지배된다. (재귀 트리는 리프가 많다.)	$f(n) = O(n^{c})$ 이고 $c 일 때 (더 작은 지수 다항식에 의해 상한)$	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)$ (분할 항은 나타나지 않는다. 재귀 트리 구조가 지배한다.)	$b=a^2$ 이고 $f(n) = O(n^{1/2-\epsilon})$ 이면, $T(n) = \Theta(n^{1/2})$ 이다.
2	문제 분할/재결합 작업이 하위 문제와 유사하다.	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 $k \ge 0$ 일 때 (임계 지수 다항식에 의해 범위가 지정되며, 0개 이상의 선택적 $\log$ 가 곱해짐)	$T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)$ (바운드는 분할 항이며, 여기서 로그는 단일 지수로 증가한다.)	$b=a^2$ 이고 $f(n) = \Theta(n^{1/2})$ 이면, $T(n) = \Theta(n^{1/2} \log n)$ 이다. $b=a^2$ 이고 $f(n) = \Theta(n^{1/2} \log n)$ 이면, $T(n) = \Theta(n^{1/2} \log^{2} n)$ 이다.
3	문제 분할/재결합 작업이 하위 문제를 지배한다. (재귀 트리는 루트가 많다.)	$f(n) = \Omega(n^{c})$ 이고 $c>c_{\operatorname{crit}}$ 일 때 (더 큰 지수 다항식에 의해 하한)	다음 조건을 만족하면, $T\left(n \right) = \Theta\left(f(n) \right)$ 이다. (합계는 분할 항 $f(n)$ 에 의해 지배된다.)	$b=a^2$ 이고 $f(n) = \Omega(n^{1/2+\epsilon})$ 이고 규칙성 조건이 참이면, $T(n) = \Theta(f(n))$ 이다.

2. 2. 1. 경우 2의 확장

Master theorem|마스터 정리^영어는 모든

k

값에 대해

f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)

일 때, 다음과 같이 세분화할 수 있다.

경우	$c_{\operatorname{crit}}$ , 즉 $\log_b a$ 와 관련된 $f(n)$ 에 대한 조건	마스터 정리 바운드	표기 예시
2a	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 임의의 $k > -1$ 일 때	... 그러면 $T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log^{k+1} n \right)$	만약 $b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log^{1/2} n)$ 이면, $T(n) = \Theta(n^{1/2} \log^{1/2} n)$ 이다.
2b	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 $k = -1$ 일 때	... 그러면 $T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \log \log n \right)$	만약 $b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log n)$ 이면, $T(n) = \Theta(n^{1/2} \log \log n)$ 이다.
2c	$f(n) = \Theta(n^{c_{\operatorname{crit}}}\log^{k} n)$ 이고 임의의 $k < -1$ 일 때	... 그러면 $T(n)= \Theta\left( n^{c_{\operatorname{crit}}} \right)$	만약 $b=a^2$ 이고 $f(n) = \Theta(n^{1/2}/\log^2 n)$ 이면, $T(n) = \Theta(n^{1/2})$ 이다.

3. 예시

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

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

3. 1. 경우 1 예시

:

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

위 공식에서:

:

a = 8, \, b = 2, \, f(n) = 1000n^2

이고,

:

f(n) = O\left(n^c\right)

이며, 여기서

c = 2

이다.

다음으로, Case 1 조건을 만족하는지 확인하면:

:

\log_b a = \log_2 8 = 3>c

이다.

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

:

T(n) = \Theta\left( n^{\log_b a} \right) = \Theta\left( n^{3} \right)

(이 결과는 점화식의 정확한 해인

T(n) = 1001 n^3 - 1000 n^2

에 의해 확인되며,

T(1) = 1

을 가정한다).

3. 2. 경우 2 예시

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

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

:

a = 2, \, b = 2, \, c = 1, \, f(n) = 10n

:

f(n) = \Theta\left(n^{c} \log^{k} n\right)

여기서

c = 1, k = 0

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

:

\log_b a = \log_2 2 = 1

이므로, c와

\log_b a

는 같다.

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

:

T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n\right) = \Theta\left( n^{1} \log^{1} n\right) = \Theta\left(n \log n\right)

따라서 주어진 점화식

T(n)

은

\Theta(n \log n)

이다.

(이 결과는 점화식의 정확한 해인

T(n) = n + 10 n\log_2 n

에 의해 확인되며,

T(1) = 1

이라고 가정한다.)

3. 3. 경우 3 예시

:

T(n) = 2 T\left(\frac{n}{2}\right) + n^2

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

:

a = 2, \, b = 2, \, f(n) = n^2

:

f(n) = \Omega\left(n^c\right)

, 여기서

c = 2

이다.

다음으로, Case 3 조건을 만족하는지 확인한다.

:

\log_b a = \log_2 2 = 1

이므로,

c > \log_b a

이다.

규칙성 조건도 만족한다.

:

2 \left(\frac{n^2}{4}\right) \le k n^2

,

k = 1/2

를 선택한다.

따라서 마스터 정리의 세 번째 경우에서 다음과 같은 결과를 얻는다.

:

T \left(n \right) = \Theta\left(f(n)\right) = \Theta \left(n^2 \right).

주어진 점화 관계

T(n)

은

\Theta(n^2)

이며, 이는 원래 공식의

f(n)

과 일치한다.

(이 결과는 점화 관계의 정확한 해인

T(n) = 2 n^2 - n

에 의해 확인되며,

T(1) = 1

이라고 가정한다.)

4. 적용 불가한 경우

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

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

위의 두 번째 허용 불가 예에서,

f(n)

과

n^{\log_b a}

의 차이는 비율

\frac{f(n)}{n^{\log_b a}} = \frac{n / \log n}{n^{\log_2 2}} = \frac{n}{n \log n} = \frac{1}{\log n}

으로 표현할 수 있다.

\frac{1}{\log n} < n^\epsilon

가 임의의 상수

\epsilon > 0

에 대해 성립한다는 것은 명백하다. 따라서 차이는 다항식이 아니며 마스터 정리의 기본 형태는 적용되지 않는다. 확장된 형태(사례 2b)가 적용되어 해는

T(n) = \Theta(n\log\log n)

이 된다.

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

알고리즘	점화 관계	실행 시간	비고
이진 탐색	$T(n) = T\left(\frac{n}{2}\right) + O(1)$	$O(\log n)$	마스터 정리 케이스 적용 $c = \log_b a$ , 여기서 $a = 1, b = 2, c = 0, k = 0$ ^[5]
이진 트리 순회	$T(n) = 2 T\left(\frac{n}{2}\right) + O(1)$	$O(n)$	마스터 정리 케이스 적용 $c < \log_b a$ 여기서 $a = 2, b = 2, c = 0$ ^[5]
정렬된 행렬 최적 검색	$T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)$	$O(n)$	$p=1$ 이고 $g(u)=\log(u)$ 인 경우 Akra–Bazzi 정리를 적용하여 $\Theta(2n - \log n)$ 을 얻는다.
합병 정렬	$T(n) = 2 T\left(\frac{n}{2}\right) + O(n)$	$O(n \log n)$	마스터 정리 케이스 적용 $c = \log_b a$ , 여기서 $a = 2, b = 2, c = 1, k = 0$

참조

_[1] 간행물 A general method for solving divide-and-conquer recurrences http://www.dtic.mil/[...] 1980-09
_[2] 웹사이트 Big-Oh for Recursive Functions: Recurrence Relations http://www.cs.duke.e[...] Duke University
_[3] 논문 A real elementary approach to the master recurrence and generalizations https://web.archive.[...] Chee Yap 2011
_[4] 웹사이트 Master Theorem: Practice Problems and Solutions https://people.csail[...] Massachusetts Institute of Technology (MIT)
_[5] 웹사이트 http://www.math.dart[...] Dartmouth College

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com