The Way
$f(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$이라는 다항식이 있을 때, 이 값은 선형 시간에 계산할 수 있다. 간단한 변환을 거치면 쉽게 알아차릴 수 있는데, $f(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n + 0)))$으로 변환 가능하기 때문이다. 코드는 다음과 같다. 길이 n+1의 배열은 $a_0,\;a_1,\;a_2,...,a_n$이 저장되어있는 배열이라고 하자 int poly(int x, int* arr, int n) { // n은 배열의 길이 (최고차항+1) int r = 0; for (int i = n; i > 0; --i) { r += arr[i]; r *= x; } r += arr[0]; return r; }
어떠한 알고리즘의 시간 복잡도를 구하기 위해서는 (특히 분할 정복 알고리즘의 경우) 점화식을 풀게 될 때가 많다.가령, 병합 정렬의 알고리즘 복잡도를 구하기 위해서는 다음과 같은 점화식을 풀어야 한다. $$T(n) = \begin{cases}\Theta(1)\;(n=1)\\2T(n/2) + \Theta(n)\;(n>1) \end{cases}$$ 재귀 트리를 작성한다면 직관적으로 복잡도가 $\Theta(n\log n)$임을 알 수 있지만, 마스터 정리를 이용하면 일반적인 경우의 풀이가 쉬워진다. 1. 마스터 정리$T(n) = aT(n/b) + f(n)$형태의 점화식이 있을 때, i) $f(n) = O(n^{\log_b a - \epsilon})$이면 $T(n) = \Theta(n^{\log_b a})$ii..