일지
알고리즘...5
niamdank
2021. 5. 13. 02:49
여러가지 점근적 표기법
점근적 표기법에는 대표적인 빅오 표기법 외에도 여러가지 표기법이 존재한다.
- 세타(Θ) 표기법 최고차항의 차수가 주어진 함수의 차수와 일치하는 함수들의 집합...동등(≒)
- { 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²)
※ 각 표기법은 집합으로 정의되며 동등 기호(=)는 집합의 포함 기호(∈)를 대신해 사용하는 것이므로 반드시 표기법이 우측에 위치해야 한다.