빅오(Big-oh) 표기법
빅오(Big-oh) 표기법
연산 횟수로 측정하는 표기법
- 입력 크기 n에 대해 계산 횟수가 어느 정도인지를 표현
- 점근 표기법으로 알고리즘의 수행 시간을 대략적으로 나타냄
| 표기법 | 설명 |
|---|---|
| O(1) | input n대해 계산 횟수가 일정함 |
| O(n) | input n에 대해 n과 계산 횟수가 비례함 |
| O(n**2) | input n에 대해 계산 횟수가 제곱으로 증가함 |
자료의 개수가 많은 경우는 차수가 가장 큰 항이 가장 큰 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있음
가장 영향을 크게 미치는 항만을 고려하면 충분함
표기법
| 표기법 | 형태 |
|---|---|
| O(1) | 상수형 |
| O(logn) | 로그형 |
| O(n) | 선형 |
| O(nlogn) | 로그선형 |
| O(n**2) | 2차형 |
| O(n**3) | 3차형 |
| O(n**k) | k차형 |
| O(2**n) | 지수형 |
| O(n!) | 팩토리얼형 |
대표적인 알고리즘 시간 복잡도
| 시간 복잡도 | 알고리즘 | n=32 |
|---|---|---|
| O(1) | 해시 테이블(입력 크기와 상관없이 일정한 시간) | 1 |
| O(log**2n) | 이전 탐색(로그 시간 수행 시간 증가) | 5 |
| O(n) | 순차 탐색 | 32 |
| O(nlog**2n) | 퀵 정렬 | 160 |
| O(n**2) | 선택 정렬 | 1,024 |
| O(n**3) | N의 3제곱으로 수행 시간 증가 | 32,768 |
best, average, worst의 경우
- 알고리즘의 수행 시간은 입력 자료 집합에 따라 다를 수 있음
best case
- 수행 시간이 가장 빠른 경우
- 의미가 없는 경우가 많음
average case
- 수행 시간이 평균인 경우
- 계산하기가 어려움
worst case
- 수행 시간이 가장 늦은 경우
- 가장 널리 사용되며, 계산하기 쉽고 응용에 따라 중요한 의미를 가질 수도 있음