n : 연산 횟수상수항 무시
$O(N+5)~\rightarrow O(N)$
계수 무시
$O(3N)~\rightarrow O(N)$
최고차항만 표기
$O(3N^3 + 2N^2+N+5)~\rightarrow O(N^3)$
시간복잡도 : 입력된 데이터 $N$의 크기에 따라 실행되는 조작(연산)의 수
공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양
| 빅오 표기법 | 명칭 | 설명 | 예 |
|---|---|---|---|
| $O(1)$ | 상수 시간 (Constatnt time) | 문제를 해결하는 데 오직 한 단계 처리 | |
| $O(log~N)$ | 로그 시간 (Log time) | 문제를 해결하는 데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦 | 이진탐색 |
| $O(N)$ | 선형 시간 | 문제를 해결하기 위한 입력 $N$ 만큼 단계가 필요 | 단순탐색 |
| $O(N~log~N)$ | 로그 선형 시간 | 문제를 해결하기 위한 단계의 수가 $N$번에, | |
| 그 하나의 $N$번당 단계들이 연산마다 특정 요인에 의해 줄어듦 | 퀵 정렬 | ||
| $O(N^2)$ | 이차 시간 | 문제를 해결하기 위한 단계의 수는 입력값 $N$의 제곱 | 선택 정렬 |
| $O(2^N)$ | 지수 시간 | 문제를 해결하기 위한 단계의 수는 주어진 상수값 2의 $N$제곱 |