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