마스터 정리(Master Theorem)는 재귀식으로 표현된 알고리즘의 시간복잡도를 간단하게 계산하는 방법이다.

어떤 알고리즘의 시간 복잡도 함수 T(n)이 다음과 같은 형태일 때,

이 함수 T(n)의 시간 복잡도 클래스는 다음과 같다.

예를 들어 T(n) = 8 \times T(\dfrac n4) + 5 \times n^2이라면,

a는 8이고, b^k는 4^2 = 16이므로 a < b^k가 성립되어 O(N^2)이된다.

만약 T(n)이 8 \times T(\dfrac n2) + 5 \times n^2이라면,

a는 8이고, b^k는 2^2 = 4이므로 a > b^k가 성립되어 O(N^{log_2 8})이된다.

이는 정리하면 O(N^3)이 된다.

시간복잡도 T(n)이 입력되면 마스터 정리를 통하여 시간복잡도를 간단하게 바꾸어 출력하는 프로그램을 작성하시오.

마스터 정리 timer 1s memory 32MB

마스터 정리 1s 32MB