[알고리즘] 점근적 표기

 알고리즘은 입력 크기가 아주 작을 경우엔 사실 효율성의 문제를 고려하지 않아도 된다. 그러나 많은 양의 데이터가 발생했을 경우에는 이야기가 달라진다. 그래서 이 알고리즘 수행시간을 분석하게 되는데 이때 점근적 분석을 한다.

 

증가율을 따졌을 때 보통 n, nlogn, n²,n³, 2ⁿ으로 표기하곤 한다.

증가율을 그림으로 나타내보자.

여러함수의 증가율 비교

이렇게 비교가 된다. 처음에는 크게 차이나는것 같지 않지만 숫자가 크면 클 수록 차이가 어마무시하게 차이난다. 그러나 예를 들어 알고리즘 복잡도를 표현할 때에 10n²같은 경우는 n²과 같은 취급 한다. 왜냐하면 처음에는 많이 차이나는 것같아도 n이 커지면 커질 수록 앞의 계수가 두 함수의 차이에 주는 영향이 적기 때문이다.

그러면 이제 알고리즘에서 매우 중요하기 쓰이는 3가지 표기법에 대해 알아보자.

 

1. O-표기법

읽을 때엔 '빅오 표기법'이라고 한다. 이러한 표기법은 점근적 상한을 나타낸다.

점근적 상한이란 증가율이 적어도 넘지는 않는다는 의미다.

ex)  O(g(n)):  f(n)는 적어도 g(n)의 증가율을 넘지 않는다.

 

2. Ω-표기법

읽을 때엔 '오메가 표기법'이라고 한다. 이러한 표기법은 점근적 하한을 나타낸다.

점근적 하한이라 증가율이 적어도 작지는 않는다는 의미다.

ex) Ω(g(n)):  f(n)는 적어도 g(n)의 증가율보다 작지 않다.

 

3. θ-표기법

읽을 때엔 '세타 표기법'이라고 한다. 이러한 표기법은 점근적 증가율이 이 함수에 비례한다는 의미다.

ex) θ(g(n))은 f(n)의 증가율에 비례한다. 

 

뭔말인지 이해하기 힘들다면 아래 그림을 보자. 그러면 이해하기 쉬울 것이다.