알고리즘 정리 - 점근적 표기

점근적 표기법

: 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법

 

이 표기법은 계수가 중요하지 않다. n.이 커짐에 따라 계수의 영향은 미미해지고, 점근적 표기에서 계수를 무시하는 이유이다. 

 

1. 세타 표기법(θ)

 

θ(f(n))은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합.

 

ex) 5n^2 + 4n = θ(n^2)

 

여기서 "=" 기호는 같다는 표현이 아닌 포함된다로 사용된다.

 

2. 빅오 표기법(O)

 

O(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합

 

ex) 5n^2 + 4n = O(n^2)

ex2) 7n = O(n^2)

 

최고차항의 차수가 f(n)과 일치하거나 그보다 더 작은 함수의 집합.

O-표기는 함수의 점근적 상한을 나타낸다.

 

3. 오메가 표기법(Ω)

 

Ω(f(n))은 점근적 증가율이 적어도 f(n)이 되는 모든 함수의 집합.

 

ex) 5n^2+4n = Ω(n^2)

 

최고차항의 차수가 f(n)과 일치하거나 더 큰 함수의 집합.

Ω-표기는 함수의 점근적 하한을 나타낸다.