알고리즘...5

여러가지 점근적 표기법

점근적 표기법에는 대표적인 빅오 표기법 외에도 여러가지 표기법이 존재한다.

• 세타(Θ) 표기법 최고차항의 차수가 주어진 함수의 차수와 일치하는 함수들의 집합...동등(≒)
  • { n², 3n² + 4, n² + nlogn, ... } = Θ(n²)
• 빅오(Ο) 표기법 최고차항의 차수가 주어진 함수의 차수와 같거나 작은 함수들의 집합...이하(≤)
  • { 2n², 3n, 2nlogn, ... } = Θ(n²)
• 오메가(Ω) 표기법 최고차항의 차수가 주어진 함수의 차수와 같거나 큰 함수들의 집합...이상(≥)
  • { n² + n, 3n³ + 4n, 6n⁴ + logn, ... } = Θ(n²)
• 리틀오(ο) 표기법 최고차항의 차수가 주어진 함수의 차수보다 작은 함수들의 집합...미만(＜)
  • { 3n, 2nlogn, ... } = Θ(n²)
• 리틀오메가(ω) 표기법 최고차항의 차수가 주어진 함수의 차수보다 큰 함수들의 집합...초과(＞)
  • { 3n³ + 4n, 6n⁴ + logn, ... } = Θ(n²)

 

※ 각 표기법은 집합으로 정의되며 동등 기호(=)는 집합의 포함 기호(∈)를 대신해 사용하는 것이므로 반드시 표기법이 우측에 위치해야 한다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘