마스터 정리(Master Method)란? 마스터 정리는 재귀식이 다음과 같은 형태일 때 적용될 수 있는 분석방법입니다.
마스터 정리는 f(n)과 nlogba를 서로 비교해서 해결하는 방법입니다. 주어진 문제에 따라 a, b, f(n) 를 nlogba 구하고 후술할 3가지 경우에 따라 답을 구하면 됩니다.
마스터 정리는 3가지 경우로 나눠서 적용할 수 있습니다. 마스터 정리의 3가지 경우 Case1 Case2 Case3 마스터 정리 예제 예제 1번 T(n)=4T(n/2)+n 예제 2번 T(n)=4T(n/2)+n2 예제 3번 T(n)=4T(n/2)+n3 예제 4번 T(n)=4T(n/2)+n2/logn 마무리 마스터 정리는 주어진 재귀식의 형태에 따라 적용 유무가 결정되는 매우 특이한 정리입니다.
그렇다 보니 모든 경우에 적용될 수 있는 풀이법이 되지는 못합니다. 하지만, 적용만 된다면 매우 빠르게 재귀식을 분석할 수 있다는 특징이 있어 알아둬야 하는 방법 중 하나입니다....
![[Algorithm] 마스터 정리(Master Method)](https://blogimgs.pstatic.net/nblog/mylog/post/og_default_image_160610.png)
#
Algorithm
#
MasterMethod
#
마스터정리
#
알고리즘
#
재귀식
#
점근성능분석
![[Data Structure]연결 리스트 발전편(Linked List Advanced)](https://mblogthumb-phinf.pstatic.net/MjAyMTEyMTVfMjM3/MDAxNjM5NTcwMjA3MDkz.YAEKookfhXVpSoIwLw9O1BMuWzAblJpfhZ_86L7aHekg.Vnf87SNXTvksLdeDo5_E3w4LzzCuaVbMDSsqh5CmtyMg.PNG.shinefilm1/image.png?type=w2)