시간복잡도 문제

이전 글 : [알고리즘] 시간복잡도와 Master Theorem [알고리즘] 시간복잡도와 Master Theorem 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 $ oneonlee.tistory.com 시간복잡도와 Master Theorem - 연습문제 출처: “Algorithms,” Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, ..

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..