The Master Theorem(마스터 정리)
이런 경우에서 시간복잡도를 편하게 구할 수 있는 공식!
where a > b> 1 and n is a no -negative integer.
case1.
a - ε라면 시간복잡도는 오른쪽과 같다.
case2.
a랑ε가 같은 경우 시간복잡도는 오른쪽과 같다.
case3.
a + ε이고 중간의 수식을 만족하는 C가 1보다 작다면 시간복잡도는 오른쪽과 같다.
Example
case1
case2
case3
Auxiliary Master Theorem
case3의 C < 1을 만족하지 못하는 경우
'아무튼 공부중 > algorithm' 카테고리의 다른 글
| [알고리즘]Matrix Multiplication with Strassen's Algorithm (1) | 2023.10.21 |
|---|---|
| [알고리즘]Quicksort (0) | 2023.10.20 |
| [알고리즘] Binary Search, Mergesort(DIvide and Conquer) (1) | 2023.10.19 |
| [알고리즘] asymptotic notation(Big O, Ω, Θ, Small O) (0) | 2023.09.20 |
| [알고리즘] Analysis of Algorithm (0) | 2023.09.13 |