시간복잡도 공식

Master Theorem $T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다 $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ $h_n = n^{log_b a}$ $f(n)$과 $h(n)$ 비교 if $f(n) h(n)$, then $O(T(n)) = f(n)$ 제약 조건 $f(n)$은 asymptotically positive function (양의 함수) 이어야 한다. $a \geq 1$ and $b > 1$이어야 한다. th..