From: CLRS - 점화식을 풀기 위한 마스터 방법

마스터 방법은 다음과 같은 형식의 점화식을 푸는 기본 지침을 제공한다.

여기서 는 상수고 은 점근적으로 양인 함수다. 마스터 방법을 사용하기 위해서는 세 가지 경우를 암기해야 하지만, 많은 경우에 연필과 종이 없이 점화식의 해를 매우 쉽게 구할 수 있다.

점화식 가 양의 상수일 때 문제 크기 을 크기가 각각 개의 하위 문제로 나누는 알고리즘의 수행 시간을 나타낸다. 개의 하위 문제는 각각 시간에 재귀적으로 풀린다. 문제를 나누고 하위 문제들의 결과를 합치는 데 드는 비용은 함수 으로 나타낸다. 예를 들어, 스트라센 알고리즘에서 도출할 수 있는 점화식은 , 이다.

기술적인 정확성의 측면에서 보면 이 점화식은 실제로 잘 정의된 것은 아닌데, 이는 이 정수가 아닐 수도 있기 때문이다. 그러나 각 a에 대한 항을 또는 으로 바꾸어도 점화식의 점근적 특성에는 영향을 주지 않는다(다음 절에서 이 주장을 증명할 것이다). 따라서 보통은 이런 형식처럼 분할정복 점화식을 쓸 때 내림과 홀림 함수를 생략하는 것이 편리하다는 것을 알 수 있다. 1

마스터 정리

가 상수고 이 함수라 하고, 음이 아닌 정수에 대해 이 다음 점화식에 의해 정의된다고 하자.

여기서 또는 을 뜻하는 것으로 이해한다. 그러면 의 점근적 한계는 다음과 같다.

  1. 상수 에 대해 이면, 이다.
  2. 이면, 이다.
  3. 상수 에 대해 이고 상수 와 충분히 큰 모든 에 대해 이면, 이다. 1

From: 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java

분할 정복을 위한 마스터 정리

분할 정복 알고리즘의 수행 시간을 계산하기 위해 다음의 정리(Theorem)가 사용될 수 있다. 주어진 프로그램(알고리즘)에 대해 먼저 문제의 재귀적 관계를 찾는다. 재귀 관계식이 다음의 형태를 지닌다면 문제를 다 풀지 않고도 바로 해답을 구할 수 있다.

재귀 관계식이 의 형태이며, 이며 가 실수라면 다음과 같다.

  • 마스터 정리 1. 이면
  • 마스터 정리 2. 일 경우
    • a. 이면
    • b. 이면
    • c. 이면
  • 마스터 정리 3. 일 경우
    • a. 이면
    • b. 이면 2

차감 정복 점화식을 위한 마스터 정리

양수 n에 대해 정의된 함수 이 어떤 상수 과 함수 에서 다음과 같은 속성을 갖는다고 하자.

안에 있다면

3

변형

이며 인 상수 에 대해 의 해답은 이다. 4

함께 읽기

  • [[big-O-notation]]

참고문헌

  • Master theorem (wikipedia)
  • Introduction to Algorithms 3판 / 토머스 코멘, 찰스 레이서손, 로날드 리베스트, 클리포드 스타인 공저 / 문병로, 심규석, 이충세 공역 / 한빛아카데미 / 2014년 06월 30일
  • 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java / 나라심하 카루만치 저 / 전계도, 전형일 공역 / 인사이트(insight) / 2014년 02월 22일

주석

  1. Introduction to Algorithms. 4.5장.  2

  2. 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java. 1.22장. 

  3. 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java. 1.24장. 

  4. 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java. 1.25장.