시간 복잡도 썸네일형 리스트형 <자료구조 알고리즘> 마스터 정리 Master theorem 점화식으로 표현되는 재귀알고리즘의 시간 복잡도를 계산하는 것은 간단한 일이 아니다. 이 글에서는 재귀알고리즘의 시간 복잡도를 조금은 쉽게 계산할 수 있게 해 주는 Master theorem에 대해 알아보자 이름은 Master theorem 이지만 모든 점화식에 사용이 가능하지는 않고 $T(n) = aT(\frac{n}{b}) + f(n)$의 형태의 점화식에만 사용가능하다. 즉 재귀 트리에서 모든 leaf노드의 차수가 같을 때만 가능한 것이다. (a: 분할한 부분 문제의 수, b: 입력의 크기가 줄어드는 비율 당연히 $\geq 2$, $T(\frac{n}{b})$ : 부분문제를 푸는데 걸리는 시간, $f(n)$ : merging에 필요한 시간) Master theorem $$T(n) = aT(\frac{n.. 더보기 이전 1 다음
