점근적 표기법
IT위키
알고리즘이 주어진 데이터 크기를 기준으로 수행시간 혹은 사용 공간이 얼마나 되는지 객관적 지표를 표현하기 위한 방법
종류
평균인 세타를 활용하면 가장 정확하고 좋겠지만 평가하기가 까다로워 측정이 쉬운 빅오를 많이 사용한다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
오메가 표기법
- 점근적 하한선 (Asymptotic lower bound)
- 빅오의 반대 개념
- 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋지 않음을 표현
세타 표기법
- 점근적 상한과 하한의 교집합 (Asymptotic tighter bound)
- 평균 범위의 개념
- 알고리즘이 아무리 좋거나 나쁜 상황이더라도 비교하는 함수 범위 안에 존재함을 표현
빅오 표기법
- 점근적 하한선 (Asymptotic upper bound)
- 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋음을 표현
