이번 게시글에서는 divide and conquer의 마지막으로 Master Theorem 에 대해 다뤄볼 예정이다. 목차는 다음과 같다.
- Master Theorem?
divide and conquer에 대한 내용은 아래 링크에서 볼 수 있다.
https://wanna-developer02.tistory.com/46
[알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort
이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에
wanna-developer02.tistory.com
1. Master Theorem?
master theorem은 재귀로 표현된 알고리즘의 time complexity를 보다 쉽게 계산하기 위한 기법이다. 점화식이 특정 모양을 하고 있을 때 사용할 수 있다는 특징이 있다.
# 조건
마스터정리를 이용하려면 점화식이 다음과 같아야 한다.
T(n) = a * T(n / b) + f(n)
점화식이 위 형태를 만족한다면 다음 세 가지 케이스로 나눌 수 있다. 여기서 ∂ > 0 이라고 가정한다.
- 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)) lg n)
- case 3 : f(n) = θ (n^(log_b (a + ∂))) 이고, a * f(n / b) <= c * f(n) 이라면, (이때 0 < c < 1) T(n) = θ(f(n))
# 예시
Ex ) T(n) = 9 T(n / 3) + n
a = 9, b = 3, f(n) = n이다. 이를 나타내면 다음과 같다. => O(n ^ (log _3 (9) - ∂ )) = n
따라서 case 1이 되고, ∂ = 1이므로 T(n) = θ(n ^ (log_3 (9))) = θ(n^2) 이다.
이렇게 챕터 1 끝!
'알고리즘' 카테고리의 다른 글
| [알고리즘] CHAP 3. Graph Theory (그래프) - 그래프로 최단거리 구하기 (1) | 2023.12.28 |
|---|---|
| [알고리즘] CHAP 2. Dynamic Programming (동적 프로그래밍) (1) | 2023.12.28 |
| [알고리즘] CHAP 1. Divide and Conquer (분할정복) - Quicksort (0) | 2023.12.26 |
| [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort (1) | 2023.12.23 |
| [알고리즘] CHAP 0. Time Complexity - Order Function ( O(n), Ω(n), θ(n) ) (2) | 2023.12.22 |