Master theorem
recursive algorithm을 구현할 때, 점화식으로부터 시간 복잡도를 구할 때 사용되는 theorem이다.
기본적으로 점화식이 다음과 같이 나올 경우에 대해서,
다음 세 가지 usecase 로 나누어서 해당 algorithm의 time complexity를 측정하는 것이 가능하다.
Example
유명하게 알려져 있는 recursive algorithm에 Master theorem을 대입하면 다음과 같다.
further questions
- 각각 다음과 같은 식으로 점화식이 분리가 되어서 나올 때는 어떻게 식을 적용해야 하는 지는 좀 헷갈린다.
T(n) = T(0.4n) + T(0.6n) + O(n)
T(n) = T(0.4n) + T(0.2n) + O(n^2)