학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다.
March 14, 2024 5:51 PM
Order (차수)
Big O - 최악
알고리즘 효율성을 상한선 기준으로 표기
g(n) <= c * f(n)
Omega - 최선
알고리즘 효율성을 하한선 기준으로 표기
g(n) >=c * f(n)
Θ (theta)
Θ(f(n)) = O(f(n)) ∩ Ω(f(n))
공통부분임 (상한, 하한)
c * f(n) <= g(n) <= d * f(n)
Small O
택도 없는 상한
g(n)이 f(n)의 small o 라면, g(n) 은 f(n) 보다 훨씬 better → 별 의미 없음
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] Dynamic Programming - Binomial Coefficient (0) | 2024.04.23 |
|---|---|
| [알고리즘] Divide and Conquer - Strassen’s Matrix Multiplication (0) | 2024.04.23 |
| [알고리즘] Divide and Conquer - Quick Sort (0) | 2024.04.23 |
| [알고리즘] Divide and Conquer - Binary Search | Merge Sort (0) | 2024.04.23 |
| [알고리즘] 알고리즘 분석 개요 (0) | 2024.04.23 |