입력 크기 N이 커질 때, 알고리즘의 성능(시간/공간)이 어떻게 증가하는지를 수학적으로 표기한 표기법
| O(1) | 상수 시간 : 입력 크기와 무관 |
|---|---|
| O(logN) | 로그 시간 : 이진 탐색 |
| O(N) | 입력 크기만큼 순회 |
| O(NlogN) | 병합 정렬, 퀵 정렬 |
| O(N^2) | 중첩 반복문(이중 for문) |
| O(2^N) | 재귀적 완전탐색(DFS, 백트래킹) 등 |
| O(N!) | 순열/조합 모든 경우 |
입력 크기(N)이 증가할 때 걸리는 시간의 증가 정도
입력 크기(N)이 증가할 때 추가로 사용하는 메모리 크기
| 1초 | 약 10^7 ~ 10^8 (1천만 ~ 1억 번 연산) |
|---|---|
| 2초 | 약 2 x 10^7 ~ 2 x 10^8 (2천만 ~ 2억 번 연산) |
| 입력 크기 N | 가능한 시간 복잡도(1초 기준) | 적용 예시 |
|---|---|---|
| N ≤ 10 | O(N!) 또는 O(2^N) 가능 | 완점탐색(브루트포스), 백트래킹, 순열/조합, DFS/BFS |
| N ≤ 100 | O(N^3) 이하 가능 | 플로이드-워셜, 3중for문 탐색, 그리디+탐색 |
| N ≤ 1,000 | O(N^2) 가능 | DP(2차원), 이중 반복문, 기본 정렬(버블,삽입) |
| N ≤ 10^4(1만) | O(NlogN) 이하 가능 | 병합 정렬, 퀵 정렬, 세그먼트 트리(쿼리 문제), 이분 탐색, 힙 |
| N ≤ 10^5(10만) | O(NlogN) 이하 필수 | 정렬 기반 문제, 투 포인터, 슬라이딩 윈도우, 해시맵, 트리 구조, 유니온 파인드 |
| N ≤ 10^6(100만) | O(N) 이하만 가능 | 카운팅 정렬, 누적합, 구간합, 소수 구하기(에라토스테네스의 체), 해시셋, 딕셔너리 |
| N ≥ 10^7(1000만) | O(1) 또는 O(logN)만 가능 | 이분 탐색, 수학적 접근, 누적값의 규칙 분석 |