마스터 정리 (+ 확장 마스터 정리)

* 마스터 정리(Master theorem)

  마스터 정리는 일반적으로 재귀적으로 호출되는 함수에 대해 시간 복잡도를 알고 싶을 때 사용합니다.

  단순 for문 중첩으로는 알 수 없는 것들을 계산해야 하는 경우가 있기 마련이죠.

  종만북에서도 다이나믹 프로그래밍 구현을 재귀 형식으로 아주 쉽게 구현, 문제에 접근할 수 있도록 해준답니다. 하지만 시간 복잡도를 계산하지 않고 재귀로 짜다보니 시간초과가 날 것만 같은 것을 증명하지 못하고 코드로 짠 다음 시간 초과를 받고서야 깨닫는 경우가 있어서 정리해봤습니다.

시간 복잡도를 계산하기 위해서는 세 가지 방식이 있는데요.

1. 치환법

2. 재귀 트리

3. 마스터 정리(또는 확장 마스터 정리)

  치환법은 점화식을 보고, 직관적으로 점화식 형태를 도출해내고 그것을 증명하는 방법입니다. 이는 자주 하지 않고서는 눈에 보이질 않습니다. 어떤 점화식이 튀어나올지가 쉽게 예상이 안가요. 하지만 검증할 때 자주 쓰이며 이상한 수식에 대해서도 해당 시간 복잡도가 증명하고자 하는 시간 복잡도의 sub-set인지를 확인할 수 있는 만능 증명법입니다.

  재귀트리법은 해당 재귀 트리의 깊이 한계, 특정 깊이 di에 대한 나올 수 있는 노드 수와 비용을 계산하고 마지막으로 리프 노드의 수 및 비용을 계산하여 시간 복잡도를  측정하는 방법인데, 다소 복잡합니다. 재귀 트리법을 사용하고 치환법으로 검증하는 것이 일반적이라고 하더군요.

  마지막으로 마스터 정리는 위의 방법 중에서 가장 간단합니다. 근의 공식처럼 외우기만 해주면 시간복잡도가 술술 나옵니다. 하지만 조건이 다소 까다롭다보니 처리하지 못하는 부분이 존재합니다. 이를 극복하기 위해서 확장 마스터 정리가 나왔더군요. 이 포스팅에서는 마스터 정리에 대해 설명하고자 합니다.

  마스터 정리를 사용하기 위해선 시간 복잡도 점화식이 아래처럼 정의되어야 합니다.

* 

  또한 마스터 정리를 쓰기 위해선 세 가지 제약 조건이 있습니다. 

1. f(n)은 다항식(polynomial function)이어야 합니다. 단 f(n)이 다항식이 아니더라도 극명하게 적용될 수 있음을 증명하면 사용할 수 있다곤 합니다. (또는 )

2. a>=1와 b>1인 양의 실수이어야만 합니다. 재귀를 호출할 때 그 호출 비용이 현재보다 작아야 한다는 것을 의미합니다. b가 1보다 작거나 같으면 오히려 문제가 그대로거나 커지니까 안됩니다.

3. 정규 조건(Regularity condition)인 을 만족하는 을 만족하는 c가 존재해야 합니다. 이 역시 부분 문제가 현재 문제보다 작아져야 함을 의미합니다. 현재 문제를 푸는 것보다 부분 문제를 푸는 데에 시간이 적게 들어가야 한다는 거죠. 만약 f(n)이 주기 함수이거나 지수 함수의 경우 의심해볼만합니다.

  마스터 정리는 다음과 같습니다. 양의 정수(입실론)에 대해 

로 시간 복잡도를 계산할 수 있습니다.

  반드시 명심해야할 점은 이 다항적으로 계산이 가능하거나 극명하게 적용될 수 있음을 확인할 수 있는 함수이어야 하며 이는 곧 과 비교하기 위함입니다. 위의 정리를 보면 모두 과 비교하여 시간복잡도를 도출하는 것을 알 수 있습니다.

* 확장 마스터 정리(Extended or Advanced master theorem)

  인 경우엔 마스터 정리를 적용할 수 없습니다. 그 이유는 다항식이 아니기 때문이죠. 그래서 비교할 수 없다고 귀결됐었습니다. 하지만 이를 확장한 확장 마스터 정리로 시간 복잡도를 구할 수 있습니다.  이를 적용하기 위해 

에 대해서 일반화를 시키면 아래와 같습니다.

* 

  여기서 와 를 비교하여 여러 개의 케이스로 나뉩니다.

1. 

2. 

3. 

* 확장 마스터 정리도 적용할 수 없는 문제

1) 

  여러 구간으로 나뉜 부분 문제에 대해서는 마스터 정리를 적용할 수 없습니다. 이 문제는 치환법으로 해결할 수 있습니다.

2) 

  b에 대해 정의할 수 없습니다. 치환법으로 해결이 가능합니다.

  (출처 Introduction to Algorithms third edition 번역 p110)

3) 

  b에 대해 정의할 수 없습니다. 치환법으로 해결이 가능합니다.

  (출처 Introduction to Algorithms third edition 번역 p110)

* 참고 문헌 및 출처

- 마스터 정리(위키) : https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

  밑에 내리다보면 확장 마스터 정리도 조금 서술되어 있음

- 확장 마스터 정리(긱앤 긱스) : https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/

- Introduction to algorithms third edition 번역 (p95~)

- https://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

- 정규 조건 : https://cs.stackexchange.com/questions/4854/why-is-there-the-regularity-condition-in-the-master-theorem

- 연습 문제 1) http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

  확장 마스터 정리를 쓸 수 없으므로, a=1, b=2, f(n)=n(2-cosn) 그리고 =1이므로 임을 자명하게 알 수 있습니다. 이제 정규 조건만 확인하면 됩니다.

  이제 모든 n에 대해 0보다 크거나 같도록하는 c값이 있는지 확인하면 됩니다. 이는 주기함수 cos에 대해 양의 정수 n를를 집어 넣으면 위 수식이 틀렸음을 알 수 있습니다. 눈으로 보는 것이 편하니 그래프로 보여주면 아래와 같습니다.

[출처 - https://www.wolframalpha.com/]

- 연습 문제 2) https://www.gatevidyalay.com/masters-theorem-solving-recurrence-relations/