-> 알고리즘이 얼마나 효율적인지 따져보기 위함 !
0. 정리
(최고 차항만 비교하면 됨)
𝑂(𝑔) = g가 upper bound / worst case !
Θ(𝑔) = tight bound
Ω(𝑔) = g가 lower bound / best case !
1. O-natation (𝑂(𝑔)=f)
-def : g(n) is asymptotic upper bound of f(n)
=
-ex (proof)
걍 pdf보기로함
'2-2 > 알고리즘' 카테고리의 다른 글
| Sorting in linear time (0) | 2021.10.16 |
|---|---|
| quick sort (0) | 2021.10.15 |
| Heapsort (0) | 2021.10.12 |
| Solving recurrences (0) | 2021.10.10 |
| Sorting 알고리즘 (0) | 2021.10.08 |