마스터 정리의 개념 앞에서 정렬이나 탐색 등을 배우며 시간 복잡도에 대해 이야기한 적이 있었죠. 마스터 정리는 big-O 를 손쉽게 구할 수 있는 정리입니다. 마스터 정리란 어떤 것인지 한번 살펴보죠. 여기서a는 나누어지는 문제의 개수를 의미하고 b는 나누어지는 문제의 크기를 의미합니다.f(n)은 나누고 나서 부가적인 과정을 의미합니다.위 식에서 알 수 있는 것은, a*T(n/b)와 f(n)중 차수가 더 큰 것이 시간 복잡도의 결과로 나타난다는 것을 볼 수 있습니다. 차수가 크면 클수록 숫자가 커질 때의 증가폭이 더 크기 때문이겠죠. 위의 식을 좀 더 정리하면 아래의 식으로 간단하게 나타낼 수도 있습니다. 마스터 정리를 이용한다면 점화식을 통하지 않더라도 바로 시간 복잡도를 구할 수 있겠죠. 공식을 ..
