나무모에 미러 (일반/밝은 화면)
최근 수정 시각 : 2025-02-09 07:10:42

마스터 정리

1. 개요2. 설명
2.1. 배경2.2. 마스터 정리2.3. 정성적 해석
3. 일반화
3.1. 바닥·천장 함수가 포함된 형태
4. 관련 문서

1. 개요

Master theorem[1]

특정 형태의 점화식을 점근적으로 푸는 공식. 주로 분할 정복 알고리즘의 시간 복잡도를 구하는데 사용한다.

2. 설명

2.1. 배경

크기가 [math(n)]인 입력 [math(X)]에 대한 분할 정복 알고리즘의 의사코드는 다음과 같다.
function F(X):
  if F(X)가 간단:
    return F(X)의 값
  else:
    X1, X2, ..., Xk := X의 분할
    Y1, Y2, ..., Yk := F(X1), F(X2), ..., F(Xk)
    Y := Y1, Y2, ..., Yk로 구한 F(X)의 값
    return Y

많은 문제에서 입력의 크기가 충분히 작을 때([math(n \le n_0)]) [math(F(x))]를 자명하게 구할 수 있다.[2] 또한, 부분 문제들은 크기가 [math(n/b)]인 부분 문제 [math(a)]개로 나누고 [math(f(n))]의 추가 시간이 걸리는 형태가 많다. 즉, 의사코드가 다음과 같이 작성된다.
function F(X):
  if X의 크기 <= n0
    return F(X)의 값
  else:
    X1, X2, ..., Xa := X의 분할 (각 Xi의 크기는 n/b)
    Y1, Y2, ..., Yk := F(X1), F(X2), ..., F(Xa)
    Y := F(X1), F(X2), ..., F(Xa)로 F(X)를 구한 값
    return Y

이 알고리즘의 실행시간 [math(T(n))]은 다음과 같이 재귀적으로 표현된다.

[math(\displaystyle
T(n) = \begin{cases}
\Theta(1) & n \le n_0\\
a T(n/b) + f(n) & \text{otherwise}
\end{cases})]

(앞으로 [math(n \le n_0)]은 무조건 [math(T(n) = \Theta(1))]으로 두고 생략한다.) 이 형태를 마스터 점화식(master recurrence)이라고 한다. 알고리즘의 실행시간을 분석하기 위해 점화식을 푸는 방법에는 치환법[3]이나 수형도를 그리는 방법[4]도 있지만, 마스터 점화식에 대해서는 마스터 정리를 적용하여 빠르게 풀 수 있다.

2.2. 마스터 정리

상수 [math(a \ge 1)], [math(b > 1)]과 함수 [math(f(n))]에 대해, 점화식 [math(T(n) = aT(n/b) + f(n))]의 점근적 일반항은 다음과 같다.
  1. 어떤 [math(\varepsilon > 0)]에 대해 [math(f(n) = O(n^{\log_b a - \varepsilon}))]이면, [math(T(n) = \Theta(n^{\log_b a}))]이다.
  2. 어떤 [math(k \ge 0)]에 대해 [math(f(n) = \Theta(n^{\log_b a} \log^k n))]이면, [math(T(n) = \Theta(n^{\log_b a} \log^{k+1} n))]이다.
  3. 어떤 [math(\varepsilon > 0)]에 대해 [math(f(n) = \Omega(n^{\log_b a + \varepsilon}))]이고, 어떤 [math(c < 1)]와 충분히 큰 [math(n)]에 대해 [math(af(n/b) \le cf(n))]이면, [math(T(n) = \Theta(f(n)))]이다.

2.3. 정성적 해석

정리에서 볼 수 있듯, [math(f(n))]과 [math(n^{\log_b a})]를 비교하여 경우를 나누는 것이 중요하다. 그 둘 중 어떤 것이 더 빠르게 증가하는지에 따라 최종 시간 복잡도가 달라지기 때문이다.

따라서 재귀 트리에서 시간을 차지하는 위치에 따라 경우가 나뉜다고 볼 수 있다.
  1. 아래쪽이 무거움: 분수령 함수가 크므로, 구동 함수 자체보다 트리에서 뻗어나가는 부분 문제들의 개수가 중요해진다. 최종 시간 복잡도가 분수령 함수를 따라간다.
  2. 균형잡힘: 경우 1과 3 사이, 구동 함수가 분수령 함수에 [math(\log n)]이 몇 번 곱해진 형태라면, 최종 시간 복잡도는 거기에 [math(\log n)]을 한 번 더 곱한 것이다.
  3. 위쪽이 무거움: 재귀 트리가 빠르게 줄어들기 때문에 구동함수를 따라간다.

3. 일반화

3.1. 바닥·천장 함수가 포함된 형태

부분 문제로 분할된 크기가 바닥 함수([math(\lfloor\cdot\rfloor)])나 천장 함수([math(\lceil\cdot\rceil)])로 표현되는 경우가 있다. 사실 배열, 트리, 그래프 등의 크기는 이산적이므로 그런 경우가 대부분이다. 다행히도, 그 함수들을 무시하고 마스터 정리를 사용할 수 있음이 증명되어있다. 즉, 아래 두 점화식은 동일하게 분석할 수 있다.

[math(\begin{aligned}
T(n) &= a' T(\lfloor n/b \rfloor) + a'' T(\lceil n/b \rceil) + f(n) \\
T(n) &= a T(n/b) + f(n)
\end{aligned})]

여기서 [math(a = a' + a'')]이다.

4. 관련 문서

[1] Master method라고도 한다.[2] 예를 들어, 크기가 [math(1)]인 배열의 최댓값은 그 배열의 원소고, 두 [math(1 \times 1)] 행렬의 행렬곱은 두 원소의 곱이다.[3] 예측한 시간 복잡도를 점화식에 대입해서 모순이 없는지 확인하는 방법 (말은 거창하지만 그냥 찍기 노가다)[4] 맨 위에 문제를 놓고 부분 문제마다 아래로 가지를 쳐서 높이마다 합을 구하는 방법

분류