※ 이 글은 chatGPT를 기반으로 작성한 글입니다.
① 일반 마스터 정리(generalized master theorem)는 고급 마스터 정리(advanced master theorem)와 확장 마스터 정리(extended master theorem)으로도 불린다.
㉠ 일반 마스터 정리는 여러 가지 형태가 있으며, 비교적 이해하기 쉬운 형태를 소개할 것이다.
② 일반 마스터 정리는 마스터 정리에서 발전된 형태로 재귀 문제를 좀 더 포괄적인 방법으로 설명한다.
㉠ 광범위한 분할 정복 알고리즘의 시간 복잡도를 구할 수 있다.
ⓐ n은 문제의 크기를 말한다.
ⓑ a는 재귀에서 생성되는 하위 문제의 크기다.
ⓒ b는 재귀의 매 단계에서의 하위 문제 크기를 의미한다.
ⓓ n/b는 문제의 크기에 대한 하위 문제의 크기를 나타난대.
ⓓ n^k *log^(p)(n)는 재귀 호출 이외에 사용되는 작업 비용이다.
③ 일반 마스터 정리는 크게 세 가지 경우로 귀결된다.
㉠ a>b^k 일 경우 T(n) = Θ(n^logb(a))이다.
㉡ a<b^k일 경우 p>=0인 상황과 p<0 인 상황으로 분류된다.
㉢ a=b^k일 경우 p가 -1을 기준으로 3개의 상황으로 분류된다.
'All about Data Structure & Algorithm > 심화' 카테고리의 다른 글
홀짝 정렬(Odd-Even sort) (0) | 2023.03.31 |
---|---|
향상된 퀵 정렬 (0) | 2023.03.24 |
셸 정렬(Shell Sort) (0) | 2023.03.24 |
분할 정복(Divide and conquer) (2) | 2023.03.15 |
마스터 정리(Master Theorem) (0) | 2023.03.14 |