Master Theorem [마스터 정리]

알고리즘은 아니지만, 재귀 문제의 시간 복잡도를 계산하는데에 큰 도움이 되는 theorem입니다.

 

위와 같은 식이 있을 때, master theorem에서 필요한 값은 a와 b, f(n)입니다.

여기서 3가지 경우로 나누어집니다.

 

ε는 0이상의 상수이며, f(n)이 어느 식에 해당하는지 확인해야 합니다.

먼저 Case 1과 Case 2에 해당할 때엔,

간단하게 위와 같은 시간 복잡도가 구해집니다.

 

다만 Case 3일때는 추가적인 조건이 필요합니다.

위에서 제시한 Case3 조건과 위 조건에 전부 해당하면 시간 복잡도는 위와 같습니다.

 

 

 

Case 1,2,3에 속하지 않다면, 위의 Auxiliary Master Theorem를 참고하시길 바랍니다.