오식랜드
[알고리즘] 점근적 표기 Big-Oh 본문
반응형
점근적 표기
- 입력 크기(n)가 무한대로 커질 때의 복잡도를 간단히 표기하기 위한 표기법
- 보통은 다항식이나 간단한 함수로 표기
- 복잡도의 상한선을 표기
Big-Oh
- 충족 조건
- cf(n) ≥ g(n)
- c > 0
- n ≥ 1
- 타이트한 값으로 설정
- cf(n^2)이나 cf(n^3)도 g(n) 보다 클테지만, 타이트한 cf(n)을 사용
다양한 표기법
- Big-Oh : 상한선
- 오메가 : 하한선
- 세타 : 빅오-오메가 사이에 속하는 식
반응형
'dev-log > cs' 카테고리의 다른 글
| [알고리즘] 정렬 알고리즘 (0) | 2023.10.21 |
|---|---|
| [알고리즘] Divaide-and-Conquer (0) | 2023.10.21 |
| [알고리즘] 시간 복잡도 (0) | 2023.10.20 |
| [알고리즘] 피보나찌 수 구하기 (0) | 2023.10.20 |
| [알고리즘] 순차탐색 / 이분탐색 (0) | 2023.10.20 |
'dev-log/cs' Related Articles
more
Comments