시간 복잡도를 표현하는 방법.
두 알고리즘 A와 B를 비교하는 방법이다.
(어떤 알고리즘이 더 빠른가)
1. 단계
(1) 수행되는 연산(산술, 비교, 대입)의 개수를 대략적으로 판단한다.
(2) 가장 큰 차수의 항만 남기고 나머지는 무시한다.
ex) 'N^2 + 2N + 1'에서 제곱항만 남기고 나머지는 소거한다.
2. 의의
(1) n-t 그래프
데이터 갯수에 따른 시간 소모에 관한 그래프이다.
n = 1,000,000 부터 큰 시간이 소요된다.(n^2 일 때 16.7min, n log n 일 때 19.93ms)
즉, 시간 복잡도가 log n 또는 n에 근접할수록 빠르게 작동한다고 알 수 있다.
3. 표기
'자료구조와 알고리즘' 카테고리의 다른 글
| 1-6. 스택(Stack) (0) | 2023.07.04 |
|---|