점근표기법(Asymptotic notation) 이란?

1. 점근표기법

Asymptotic notation

점근표기법(Asymptotic notation)이란 알고리즘의 시간복잡도, 공간복잡도를 표현하는데 사용되는 표기법이다. 시간복잡도란 알고리즘이 문제를 해결할 때 어느 정도의 시간이 소요되는지를 의미하며, 공간복잡도란 알고리즘이 문제를 해결할 때 얼마나 많은 메모리를 차지하는지를 의미한다. 최근에는 메모리의 용량이 크고 빠르기 때문에 공간복잡도 보다는 시간복잡도를 조금 더 먼저 고려하는 경향을 보이고 있다. 이런 알고리즘의 효율성은 데이터의 개수와 기본 연산의 횟수에 따라서 결정된다.

 

이러한 점근 표기법을 사용하는 데에는 크게 3가지 이유가 있다. 
1. 성능 비교
다양한 알고리즘이 있을 때, 이를 비교해서 가장 좋은 성능을 가지는 알고리즘을 선택해야 한다. 이럴 때 우리는 알고리즘끼리의 성능을 비교하기 위해 점근 표기법으로 표현된 시간복잡도, 공간복잡도를 비교하게 된다.
2. worst case의 시간 복잡도 파악
알고리즘에서는 best case, average case, worst case 세 가지 경우를 고려하게 된다. 그 중에서도 가장 최악을 가정하는 worst case를 고려해서 최악인 상황에서도 효율적으로 작동하는 알고리즘을 선택해야 할 필요성이 있다.
3. 입력 크기 증가에 따른 알고리즘 성능 예측
입력된 데이터가 커져도 알고리즘이 이를 잘 해결할 수 있을지도 파악을 해야 한다. 그렇기 때문에 점근 표기법을 이용하면 데이터의 크기가 증가했을 때에 어느정도의 성능을 보일 지 짐작할 수 있게 된다.

 

대표적으로 빅오 표기법(Big-O notation), 빅오메가 표기법(Big-Omega notation), 빅세타 표기법(Big-Theta notation)을 들 수 있다. 이 외에도 작은오메가 표기법(Little-Omega notation)나 작은오 표기법(Little-O notation)등이 있다.

 

2. 빅오 표기법

Big-O notation

빅오 표기법은 가장 대표적으로 사용되는 점근표기법으로, 최악의 경우에도 이 기준을 넘지는 않을 것이다, 라는 의미로 사용된다. 상한선을 제시해 주기 때문에 점근적 상한(asymptotic upper bound)이라고 한다. n이 충분히 큰 상태를 가정하기 때문에 영향력이 적은 낮은 차수의 항이나 상수항을 무시한다. 그렇기 때문에 계산이 간단하고, 알고리즘의 성능을 간단하게 파악할 수 있는 장점이 있어 많이 사용된다.

수학적 정의

모든\$ n,\ n\ge {n}_0$ 에 대해 $\ f\left(n\right)\le cg\left(n\right)$ 인 조건을 만족하는 두 양의 상수 $c$와 ${n}_0$ 가 존재 하면 $\ f\left(n\right)=O \left(g\left(n\right)\right)$ 이다.

위의 그래프에서 f(n)은 내가 만든 알고리즘의 시간 효율성을 나타내는 함수이다. 이 때 어떠한 양수 ${n}_0$보다 큰 입력값이 들어가게 되면 어떠한 경우라도 점근상한선을 넘지 못하게 되는데, 이럴 때를 f(n) = O(g(n))이라고 표시한다. 

 

3. 빅오메가 표기법

Big-Omega notation

빅오메가 표기법의 경우에는 위의 빅오 표기법과는 다르게 최소한 이정도 이상이 걸릴 것이다, 라는 의미로 사용된다. 하한선을 제시해 주기 때문에 점근적 하한(asymptotic lower bound)라고 한다. 

수학적 정의

모든$\ n,\ n\ge {n}_0$에 대해 $\ f\left(n\right)\ge cg\left(n\right)$인 조건을 만족하는 두 양의 상수 $c$와 ${n}_0$가 존재하면 $ f\left(n\right)=\Omega \left(g\left(n\right)\right)$ 이다.

임의의 양수 ${n}_0$보다 큰 입력값이 들어가게 되면 어떠한 경우라도 f(n)은 cg(n)이상이게 되며, 이럴 때를 f(n)=Ω(g(n))이라고 표시한다. 

 

4. 빅세타 표기법

Big-Theta notation

빅세타 표기법의 경우에는 빅오 표기법과 빅오메가 표기법의 중간으로, 시간 복잡도의 상한과 하한을 동시에 표현한다. 특히 시간복잡도가 최선인 경우와 최악의 경우가 다른 경우에 빅세타 표현법을 활용하면 최선과 최악을 모두 나타낼 수 있게 된다. 상한과 하한의 범위를 모두 나타내기 때문에 점근적 상한 및 하한(asymptotic tight bound)이라고 한다. 빅세타 표기법은 최선, 최악을 동시에 고려할 수 있어 정확한 분석이 가능하지만 보다 복잡한 분석이 필요하기도 하고, 최선과 최악의 경우 차이가 크지 않거나 정확한 분석이 필요하지 않은 경우에는 빅오 표기법을 이용하기 때문에 상대적으로는 적게 사용된다. 

수학적 정의 

모든$\ n,\ n\ge {n}_0$에 대해 ${C}_1​g(n) ≤ f(n) ≤ {C}_2​g(n)$을 만족하는 세 양의 상수​ ${C}_1,\ {C}_2$와 $\ {n}_0$가 존재하기만 하면 $\ f\left(n\right)=\Theta \left(g\left(n\right)\right)$이다.

임의의 양수  ${n}_0$이상의 값이 들어가게 되면, 알고리즘의 성능이 어떠한 경우라도 g(n)의 범위 내에 있다는 것을 의미하게 된다. 

 

5. 그 외

Little-Omega notation & Little-O notation

리틀오메가 표기법과 리틀오 표기법의 경우에는 빅오메가, 빅오 표기법과 동일하게 하한/상한을 제시하는 표기법이다. 하지만 각 정의에서 등호가 빠지게 되어 더 엄격한 정의를 나타낸다. 

 

6. 추가적으로 읽어보면 좋을 포스트

https://chayan-memorias.tistory.com/100

https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/