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