dev-log/cs
[알고리즘] 점근적 표기 Big-Oh
개발하는 오식이
2023. 10. 21. 00:02
반응형
점근적 표기
- 입력 크기(n)가 무한대로 커질 때의 복잡도를 간단히 표기하기 위한 표기법
- 보통은 다항식이나 간단한 함수로 표기
- 복잡도의 상한선을 표기
Big-Oh
- 충족 조건
- cf(n) ≥ g(n)
- c > 0
- n ≥ 1
- 타이트한 값으로 설정
- cf(n^2)이나 cf(n^3)도 g(n) 보다 클테지만, 타이트한 cf(n)을 사용
다양한 표기법
- Big-Oh : 상한선
- 오메가 : 하한선
- 세타 : 빅오-오메가 사이에 속하는 식
반응형