빅오메가 표기법 (Big Omega)
※ 수학적 정의 : 모든 n ≥ n0에 대하여 |f(n)| ≥ C|g(n)|을 만족하는 2개의 상수 C와 n0가 존재하면 f(n) = Ω(g(n))이다.
▶ 함수의 하한 (lower bound)을 표시한다.
▶ 예를 들어, f(n) = 2n +1일 때, n ≥ 5이면 2n + 1 < 10n이므로 f(n) = Ω(n)이다.
▶ 빅오 표기법이 Worst Case에 대한 표기법이라면, 빅오메가 표기법은 Best Case에 대한 표기법이다.
빅세타 표기법 (Big Theta)
※ 수학적 정의 : 모든 n ≥ n0에 대하여 C1|g(n)| ≤ |f(n)| ≤ C2|g(n)|을 만족하는 3개의 상수 C1, C2와 n0가 존재하면 f(n) = Θ(g(n))이다.
▶ 함수의 상한인 동시에 하한을 표시한다.
▶ 예를 들어, f(n) = 2n + 1일 때, n ≥ 1이면, n ≤ 2n +1 ≤ 3n 이므로 f(n) = Θ(n)이다.
▶ f(n) = O(g(n)) 이면서 f(n) = Ω(g(n)) 이면 f(n) = Θ(g(n)) 이다.
▷ 예시 1) f(log n)이 O(log n)이면서 Θ(log n)이면 Ω(log n)이다.
▷ 예시 2) O(n)이면서 Θ(n^2)이면 빅세타 표기법으로 나타낼 수 없다.
참고 서적 : <C언어로 쉽게 풀어쓴 자료구조>
'Programming > 자료구조' 카테고리의 다른 글
| [자료구조] 06. 재귀 (Recursion) (0) | 2021.10.23 |
|---|---|
| [자료구조] 05. 알고리즘의 효율성 (최선, 평균,최악) (0) | 2021.10.22 |
| [자료구조] 03. 알고리즘의 성능 분석(시간 복잡도, 빅오 표기법) (0) | 2021.10.20 |
| [자료구조] 02. 추상 데이터 타입 (0) | 2021.10.20 |
| [자료구조] 01. 자료 구조와 알고리즘 (0) | 2021.10.12 |
