마스터 정리 timer 1s memory 32MB

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

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

• T(n) = a \times T(\dfrac nb) + c \times n^k

• a, b, c, k는 상수이며, 0<a, 0<c, 2{\le}b, 0{\le}k)

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

• T(n) ∈ θ(n^k), if a < b^k

• T(n) ∈ θ(n^k log_2n)​, if a = b^k

• T(n) ∈ θ(n^{log_b a})​, if a > b^k

예를 들어 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)이 입력되면 마스터 정리를 통하여 시간복잡도를 간단하게 바꾸어 출력하는 프로그램을 작성하시오.​