빅오 표기법(Big-O Notation)
입력 크기 N이 커질 때, 알고리즘의 성능(시간/공간)이 어떻게 증가하는지를 수학적으로 표기한 표기법
O(1) | 상수 시간 : 입력 크기와 무관 |
O(logN) | 로그 시간 : 이진 탐색 |
O(N) | 입력 크기만큼 순회 |
O(NlogN) | 병합 정렬, 퀵 정렬 |
O(N^2) | 중첩 반복문(이중 for문) |
O(2^N) | 재귀적 완전탐색(DFS, 백트래킹) 등 |
O(N!) | 순열/조합 모든 경우 |
시간 복잡도
입력 크기(N)이 증가할 때 걸리는 시간의 증가 정도
공간 복잡도
입력 크기(N)이 증가할 때 추가로 사용하는 메모리 크기
1초 시간 제한일 때, 얼마나 많은 연산을 처리할 수 있는가?
일반적인 기준
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)만 가능 | 이분 탐색, 수학적 접근, 누적값의 규칙 분석 |
시간복잡도를 이용해 어떻게 판단해야하는가?
1.
입력 크기별로 필요한 시간복잡도 감 잡기
a.
대략 이 입력엔 어떤 알고리즘이 필요하겠다
2.
대표적인 알고리즘의 시간복잡도 기억하기
•
정렬 : O(NlogN)
•
이분 탐색 : O(logN)
•
DFS/BFS(노드 수 V, 간선 수 E) : O(V + E)
•
DP : 보통 O(N) or O(N^2)
•
해시/딕셔너리 탐색 : O(1)
•
에라토스테네스의 체 : O(N log log N)
•
순열/조합 : O(N!), O(2^N)
3.
실전에서 시간 제한으로 판단하는 감각 익히기
a.
입력 크기가 이 정도 → 이 정도 시간 복잡도 이하로 풀어야겠다