마스터 정리

위키백과 ― 우리 모두의 백과사전.

알고리즘 분석에서 마스터 정리(Master theorem)는 재귀 관계식으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법이다. 잘 알려진 알고리즘 교과서 Introduction to Algorithms의 4.3절과 4.4절에 설명되어 유명해졌으나, 이 방법이 모든 재귀 관계식을 풀 수 있는 건 아니다.

[편집] 내용

다음과 같은 관계식이 주어졌다고 하자.

T(n) =  \begin{cases} \Theta(1) & \mathrm{if}\quad n=1\\ aT(n/b) + f(n) & \mathrm{otherwise} \end{cases}

여기서 a \geq 1, b > 1이고 f(n)은 점근적으로 양수 함수값을 가지는 함수이다. 이 때 다음과 같은 경우에 대해 점근적 수행 시간을 계산할 수 있다.

  1. 만약 어떤 상수 ε > 0에 대해 f(n) \in O\left( n^{\log_b a - \epsilon} \right)이면, T(n) \in \Theta\left( n^{\log_b a} \right)이다.
  2. 만약 f(n) \in \Theta\left( n^{\log_b a} \right)이면, T(n) \in \Theta\left( n^{\log_b a} \log(n)\right)이다.
  3. 만약 어떤 상수 ε > 0에 대해 f(n) \in \Omega\left( n^{\log_b a + \epsilon} \right)이고, c > 1과 충분히 큰 n에 대해 a f\left( \frac{n}{b} \right) \le c f(n)이 성립하면, T(n) \in \Theta(f(n))이다.

[편집] 바깥 고리

이 문서는 컴퓨터에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.