일반 마스터 정리(Generalized Master theorem)

※ 이 글은 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개의 상황으로 분류된다.