[자료구조 및 알고리즘] (5) Master Method (마스터 정리)

알고리즘이 recursive하지 않으면 꽤 쉽게 O(...)을 알아낼 수 있다. (O(1), O(n)등) 그런데 recursive하게 되는 순간 어떻게 분석해야 할 지 약간 애매해진다.

그래서 나온 것이 master method - recursive한 알고리즘의 시간 복잡도를 쉽게 분석하도록 도와주는 정리이다. 1. Master method의 소개 일단 recursive algorithm에서 다음 세 가지를 알아낸다. a = recursion 한 스테이지를 지날 때마다 subproblem이 몇 개로 늘어나는지?

예를 들어 merge sort의 경우 2개로 나누어지기 때문에 a=2이다. b = 각 recursion stage에서 subproblem의 크기가 얼마나 작아지는지? 예를 들어 merge sort = 절반으로 쪼개지므로 b=2이다. d = 마지막 combine step의 복잡도를 O(n^d)로 나타낸 것. linear한 경우 d=1이다. combine은 recursion이 아...