알고리즘/Master method

// 2020년 10월 5일 월요일 3번째 글
// 작성자: 황상훈

// 이 글은 https://jeonggyun.tistory.com/42 에서 덧붙인 글입니다.

.
.
.

Master method(마스터 방법)

T(n) = a * T(n/b) + f(n) 과 같은 점화식에 적용할 수 있는 풀이 방법 중 한가지.
(a >= 1, b > 1)

마스터 메서드를 적용할 수 있는 점화식이라고 여겨질 때, 우선 n^logb(a)를 구한다.

n^logb(a)와 f(n)의 크기를 비교하며 다음 세가지 방법을 고려한다.

1. T(n)이 f(n)보다 큰 경우.
   -> T(n) = θ(n^logb(a))가 된다.

2. T(n)이 f(n)과 같은 경우.
   -> T(n) = θ(n^logb(a) * lg(n))이 된다. (여기서 lg(n)은 2를 밑으로 하는 로그이다.)

3. T(n)이 f(n)보다 작은 경우.
   -> T(n) = θ(f(n))이 된다.
   하지만, 3의 경우에는 다음을 한번 더 점검해야 한다.
   a f(n/b) <= c f(n)을 만족하는지 점검한다. (이 때, c < 1인 상수)

마스터 메서드를 적용하지 못하는 경우도 있다.

점화식이 방법 1과 2의 사이에 있거나 2와 3의 사이에 있는 경우이다.

이는, T(n)이 f(n)보다 다항식적으로 충분히 크거나 작지 않은 경우에 생긴다.

.
.
.

// 부족하거나 모르는 내용에 대한 자유로운 댓글은 환영입니다.
// 출처에서 문제가 발생하면 적당한 조치를 취하겠습니다.