Master Theorem

반복문의 시간복잡도를 계산하는건 비교적 간단한 일입니다.

재귀호출의 시간복잡도를 계산하는건 매우 까다롭습니다.

depth d 까지 n번 반복하라 느낌의 재귀의 경우
O(d^n) 라고 예상할 수 있지만 많은 경우 재귀호출의 시간복잡도는 상당히 까다롭습니다.

그래서 Master Theorem 이 있습니다.

어떤 함수의 수행 시간이 특정 형태의 함수로 표현될 때 이 함수의 O 표기법을 쉽게 계산할 수 있게 해줍니다.

모든 재귀함수의 시간을 알 수 있는건 아닙니다.

Master Theorem
T(n) = aT(n/b) + f(n)
여기서 a ≥ 1, b > 1이며, f(n)은 양의 함수입니다.

T(n/b) n보다 작은 범위에서 재귀호출하며 재귀호출 말고도 f(n) 라는 작업을 하는 함수를 의미합니다.

세 가지 경우
마스터 정리는 f(n)과 n^(log_b a)의 관계에 따라 세 가지 경우로 나뉩니다:

• Case 1: f(n) = O(n^(log_b a - ε))일 때, T(n) = Θ(n^(log_b a))
• Case 2: f(n) = Θ(n^(log_b a))일 때, T(n) = Θ(n^(log_b a) * log n)
• Case 3: f(n) = Ω(n^(log_b a + ε))이고 af(n/b) ≤ cf(n)일 때, T(n) = Θ(f(n))

사용 방법
a, b, f(n)을 식별합니다.
n^(log_b a)를 계산합니다.
f(n)과 n^(log_b a)를 비교하여 적절한 경우를 선택합니다.
해당 경우의 공식을 적용하여 시간 복잡도를 구합니다.

적용 예시

• 병합 정렬: T(n) = 2T(n/2) + n, 결과는 O(n log n)입니다.
• 이진 검색: T(n) = T(n/2) + 1, 결과는 O(log n)입니다.