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