점근 표기

점근 표기법이라고 하면 와닿지 않아도

 

아마 시간 복잡도 혹은 O(n) 이라면 익숙하실 것 같습니다.

 

 

점근 표기법에 대해 알아봅시다.

 

 

-점근 표기법의 종류

𝜪	빅오 (Big-Oh)	Upper Bound (상한)
𝜴	빅오메가 (Big-Omega)	Lower Bound (하한)
𝜭	세타 (Theta)	Tight Bound (딱 맞는)

 

 

-빅오 표기법

Definition of Big-O by Foundations of Algorithms

빅오 표기법은 최악의 경우(상한)을 나타내는 표기법입니다.

 

이떄 상한이라는 말의 의미는, 아무리 느려도 빅오 표기법으로 표현한 것보다는 빠르다는 것입니다.

 

보통 어떤 알고리즘의 실행 시간이 주어졌을 때 가장 높은 차수를 사용합니다.

빅오 표기법 예시 / 출처 : 홍정모 알고리즘 강의

 

 

-빅오메가 표기법

Definition of Big-Omega by Foundations of Algorithms

빅오메가 표기법은 최선의 경우(하한)을 나타내는 표기법입니다.

 

하한이라는 말의 의미는 아무리 느려도 빅 오메가로 표현한 것보다 빠르다는 의미입니다.

 

정의에서 볼 수 있듯 빅오 표기법에서 부등호의 방향만 바뀐 것을 확인할 수 있죠.

빅오메가 표현 예시 By 홍정모 알고리즘

빅 오메가는 하한을 나타내는 표기법이기에 다양하게 나타낼 수 있다는 것도 알아두시면 좋을 것 같습니다.

 

 

-세타

마지막으로, 세타입니다. 우선 세타의 정의부터 살펴보죠.

Definition of Theta by Foundations of Algorithms

 

정의를 보면 알 수 있듯, 하한과 상한 사이의 함수입니다. 식으로 보기 어려울 수 있지만 그림으로 보면 바로 이해가 될 것 같습니다.

아래 그림에서 볼 수 있듯, 세타는 빅오와 빅오메가의 교집합으로도 볼 수 있습니다.

 

 

출처 : Foundations of Algorithms

 

첫 번째 그래프는 big-O의 그래프입니다. 

N이상인 수에서는 cf(n)이 g(n)의 상한을 나타내고 있습니다.

 

두 번째 그래프는 big-Omega의 그래프입니다.

N이상인 수에서는 cf(n)이 g(n)의 하한을 나타내고 있습니다.

 

마지막 세 번째 그래프는 Theta 그래프입니다.

N이상인 수에서는 cf(n) <= g(n) <= df(n)인 것을 확인할 수 있습니다.

 

N보다 작은 수에서는 다르게 나올 수 있지만, 수가 커져갈수록 실행 시간도 늘어나기에

큰 수에 중점을 두고 있다는 것을 인지해야 합니다.

 

하지만, 우리가 처리해야 할 데이터의 크기가 작은 경우, 차수가 높은 알고리즘이 더 빠를수도 있으므로 위의 표기법들이 모든 수에서 절대적이다 라고 볼 수는 없을 것 같습니다.