Programming/자료구조
[자료구조] 04. 빅오메가 표기법 & 빅세타 표기법
happy_jinsu
2021. 10. 21. 16:13
빅오메가 표기법 (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언어로 쉽게 풀어쓴 자료구조>