점근적 표기법: Difference between revisions
From IT Wiki
(→빅오 표기법) |
(→빅오 표기법) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 12: | Line 12: | ||
* 빅오의 반대 개념 | * 빅오의 반대 개념 | ||
* 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋지 않음을 표현 | * 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋지 않음을 표현 | ||
=== [[세타 표기법]] === | === [[세타 표기법]] === | ||
| Line 19: | Line 20: | ||
=== [[빅오 표기법]] === | === [[빅오 표기법]] === | ||
* 점근적 | * 점근적 상한선 (Asymptotic upper bound) | ||
* 알고리즘이 아무리 나쁜 상황이더라도 비교 함수보다는 같거나 좋음을 표현 | * 알고리즘이 아무리 나쁜 상황이더라도 비교 함수보다는 같거나 좋음을 표현 | ||
Latest revision as of 15:35, 4 January 2022
알고리즘이 주어진 데이터 크기를 기준으로 수행시간 혹은 사용 공간이 얼마나 되는지 객관적 지표를 표현하기 위한 방법
종류[edit | edit source]
평균인 세타를 활용하면 가장 정확하고 좋겠지만 평가하기가 까다로워 측정이 쉬운 빅오를 많이 사용한다.
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
오메가 표기법[edit | edit source]
- 점근적 하한선 (Asymptotic lower bound)
- 빅오의 반대 개념
- 알고리즘이 아무리 좋은 상황이더라도 비교 함수보다는 같거나 좋지 않음을 표현
세타 표기법[edit | edit source]
- 점근적 상한과 하한의 교집합 (Asymptotic tighter bound)
- 평균 범위의 개념
- 알고리즘이 아무리 좋거나 나쁜 상황이더라도 비교하는 함수 범위 안에 존재함을 표현
빅오 표기법[edit | edit source]
- 점근적 상한선 (Asymptotic upper bound)
- 알고리즘이 아무리 나쁜 상황이더라도 비교 함수보다는 같거나 좋음을 표현
