점근 표기법(asymptotic notation)은 시간 복잡도 또는 공간 복잡도 함수의 증가 양상을 구분하기 위해 사용하는 표기법이다.
대표적으로 상한(O), 하한(Ω), 교집합(Θ)이 있다. 먼저 간략하게 뜻을 말하면 아래와 같다.
O(f(n)) : 상한, 아무리 느려봤자 f(n) 정도이다. f(n)보다 빠르거나 같다.
Ω(f(n)) : 하한, 아무리 빨라봤자 f(n) 정도이다. f(n)보다 느리거나 같다.
Θ(f(n)) : 차수, 상한과 하한을 함께 제시. 두 집합의 교집합
하나 하나 알아보기전에, 앞서 말한 '빠르다', '느리다'라는 표현에 대해 그 뜻을 정리할 필요가 있다. 함수의 차수가 높을수록 더 빠를 것 같지만, 차수가 낮은 것이 더 빠르다고 표현한다. 즉, 그래프 상으로 그렸을 때 더 아래에 있는 함수가 더 빠르다.
예를 들면, y=8x+2보다 y=2x+1의 그래프가 더 아래에있으므로 y=2x+1이 더 빠르다고 할 수 있다.
이 때, 어느 그래프가 더 아래에 있느냐를 따질 때에는 x 값이 무한대로 갈 때의 궁극적인 위치를 바탕으로 따져야한다.
위 그림처럼 초반에는 g(n)이 cf(n)보다 아래에있지만(더 빠르지만) N을 넘어나고나서 부터는 n이 무한으로 갈수록 cf(n)보다 위에 있으므로(더 느리므로) 궁극적으로는 'g(n)이 c(f(n))보다 더 느리다'라고 한다. 이제 각 의미에 대해 알아보자.
O(f(n)) : 점근적 상한, asympotic upper bound
g(n) ∈ O(f(n))일 때, f(n)이 g(n)의 상한이 된다.
주어진 복잡도함수 f(n)에 대해 g(n) ≤ c x f(n)을 만족하는 음이아닌 정수 n과 상수 c가 존재한다.
즉, g(n)이 f(n)보다 빠르거나 같다는 뜻.
위에서 연습했듯, g(n)이 cf(n)보다 궁극적으로 빠르다. 따라서 g(n) ∈ O(f(n)) 이다.
위 그림과 같이 O(n2)에 속하는 집합의 함수들(=g(n))은 n2(=f(n))보다 빠르거나 같다.
Ω(f(n)) : 점근적 하한, asympotic lower bound
g(n) ∈ Ω(f(n))일 때, f(n)이 g(n)의 하한이 된다.
주어진 복잡도함수 f(n)에 대해 g(n) ≥ c x f(n)을 만족하는 음이아닌 정수 n과 상수 c가 존재한다.
즉, g(n)이 f(n)보다 느리거나 같다는 뜻.
위 그래프가 바로 서론에서 예로 들었던 그래프이다. g(n)이 cf(n)보다 궁극적으로 느리다. 따라서 g(n) ∈ Ω(f(n)) 이다.
위 그림과 같이 Ω(n2)에 속하는 집합의 함수들(=g(n))은 n2(=f(n))보다 느리거나 같다.
Θ(f(n)) : 차수, asympotic tight bound
Θ(n) = O(f(n)) ∩ Ω(f(n))일 때, Θ(n)은 가능한 모든 g(n)의 집합이다.
주어진 복잡도함수 f(n)에 대해 c x f(n) ≤ g(n) ≤d x f(n)을 만족 만족하는 음이아닌 정수 n과 상수 c가 존재한다.
g(n) ∈ Θ(f(n))일 때, "g(n)은 f(n)의 차수(order)"라고 한다.
궁극적으로 g(n)이 cf(n)보다 느리고, df(n)보다 빠르다. 따라서 g(n) ∈ Θ(f(n))이다.
위 그림의 경우 교집합에 속해있는 함수들은 O(n2)이면서 Ω(n2)이고, 따라서 Θ(n2)이다.
이러한 차수는 알고리즘의 성능을 표시하고, 또 서로 비교할때에 유용한 지표로서 사용된다. O, Ω, Θ 서로 모양이 비슷해서 이게 그거같고 저게 이거같고 그렇지만 무튼 다 쓸모가 있으니... 알아두는걸로..^^ 다음엔 드디어 Divide-and-Conquer 카테고리로 넘어간다! 글 쓰기가 더욱 어려워질 것 같지만 무튼 난 이제 영화볼거다.
'알고리즘 > <1> Efficiency, Analysis, Order' 카테고리의 다른 글
| [알고리즘] 알고리즘 분석, Analysis | 최선, 최악, 평균, 모든 경우 (0) | 2020.12.23 |
|---|
