[Algorithm] 점근적 표기법(Asymptotic notation) 이해하기

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

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법으로,

중요하지 않은 상수와 계수들은 무시하면서 실행시간을 표기하는 것을 말합니다.

 

 

 

점근적 표기법의 종류는 아래와 같습니다.

Theta - f(n) = θ(g(n))

BigO -  f(n) = O(g(n))

Omega -  f(n) = Ω(g(n))

Little Oh - f(n) = o(g(n))

Little Omega - f(n) = ω(g(n))

 

 

Theta, BigOh, Omega는 자주 사용되기 때문에 더 자세히 알아보도록 하겠습니다.

 

 

 

BigO -  f(n) = O(g(n))

---

Big O는 최악의 경우에 이 기준을 넘지 않음을 의미합니다.

 

 

Omega -  f(n) = Ω(g(n))

---

Big O는 아무리 좋아도 비교하는 함수와 같거나 좋지 않음을 의미합니다.

 

 

Theta - f(n) = θ(g(n))

---

Theta는 bigO(상한)와 omega(하한)를 모두 알고 있을 때 표기하는데,

알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수 범위 안에 있음을 의미합니다.

 

 

 

◡̈