마스터 정리와 증명

마스터 정리의 개념

 

앞에서 정렬이나 탐색 등을 배우며 시간 복잡도에 대해 이야기한 적이 있었죠. 

 

마스터 정리는 big-O 를 손쉽게 구할 수 있는 정리입니다.

 

마스터 정리란 어떤 것인지 한번 살펴보죠.

 

여기서

a는 나누어지는 문제의 개수를 의미하고 

b는 나누어지는 문제의 크기를 의미합니다.

f(n)은 나누고 나서 부가적인 과정을 의미합니다.

위 식에서 알 수 있는 것은, a*T(n/b)와 f(n)중 차수가 더 큰 것이 시간 복잡도의 결과로 나타난다는 것을 볼 수 있습니다.

 

차수가 크면 클수록 숫자가 커질 때의 증가폭이 더 크기 때문이겠죠. 

 

위의 식을 좀 더 정리하면 아래의 식으로 간단하게 나타낼 수도 있습니다.

 

홍정모 알고리즘 강의

마스터 정리를 이용한다면 점화식을 통하지 않더라도 바로 시간 복잡도를 구할 수 있겠죠.

 

공식을 외우기보다는 이해하는 것이 나을 테니.. 마스터 정리 증명을 해봐야 할 것 같습니다.

 

 

 

마스터 정리의 증명

 

마스터 정리를 하기 위해 몇 가지 조건에 대해 설명하겠습니다.

 

조건

1. T(1) = O(1)  //T(1)의 연산량이 많을 수도 있지만 상수 시간이라고 가정하겠습니다.

2. n/2 에서 n이 홀수인 경우, 나누어떨어지지 않기에 버림을 이용하겠습니다.

 

 

또, 수학 공식을 하나 알아야 합니다. 바로 기하급수의 합 공식입니다. 아마 고등학교 때 배우고 기억이 잘 안나시는 분들이 많을 것 같습니다. 저 또한 그렇고요..

이 공식 기억나시나요? 기억이 안나신다면 한 번 보고 가시는 것을 추천드립니다. 

바로 뒤의 계산에서 필요하니까요.

 

이제 알고리즘의 분할 방식을 트리로 나타내보겠습니다.

레벨이 0일 때부터 더이상 분할할 수 없는 레벨에 도달할 떄까지의 과정을 트리로 표현했습니다.

 

이제 시간을 구하기 위해서는 맨 오른쪽의 계산량들을 위의 급수의 합 공식으로 구해보면 되겠죠?

 

해봅시다.

 

급수의 합 공식과 상수는 고려하지 않는다는 성질을 이용하여 증명을 해보았습니다.

 

개인적으로는 첫 번째 사진에 있는 식이 왜 저렇게 나오는지 이해하는 것이 가장 중요하다고 생각합니다.