핵심 정리
| 표기 | 대략적 의미 | 자주 나오는 형태 |
|---|---|---|
| O(1) | 입력이 커져도 일정 | 배열 인덱스 접근, 해시 평균 조회 |
| O(log n) | 절반씩 줄어듦 | 이진 탐색, 균형 트리 탐색 |
| O(n) | 한 번 훑음 | 선형 탐색, 합계 계산 |
| O(n log n) | 정렬급 비용 | 병합 정렬, 힙 정렬, 대부분의 일반 정렬 |
| O(n²) | 모든 쌍 비교 | 이중 반복문, 작은 입력의 완전 탐색 |
| O(2ⁿ), O(n!) | 부분집합·순열 탐색 | 백트래킹, 브루트포스 조합 |
성장률 읽기
Big-O는 실제 실행 시간이 아니라 입력 크기 n이 커질 때 연산량이 얼마나 빨리 증가하는지를 보는 표기입니다. 상수와 낮은 차수는 보통 지웁니다.
3n + 10 -> O(n)
2n^2 + 50n -> O(n^2)
n log n + n -> O(n log n)이렇게 지우는 이유는 입력이 충분히 커지면 가장 빠르게 커지는 항이 전체 비용을 지배하기 때문입니다. 다만 코딩 테스트에서는 상수도 완전히 무시하면 안 됩니다. 같은 O(n)이어도 문자열 복사, 정렬 호출, 큰 객체 생성이 반복되면 제한 시간 안에 실패할 수 있습니다.
최선·평균·최악
복잡도는 하나만 있는 값이 아닙니다. 어떤 입력에서는 빠르고, 어떤 입력에서는 느릴 수 있습니다.
| 관점 | 의미 | 예시 |
|---|---|---|
| 최선 | 가장 운 좋은 입력 | 찾는 값이 첫 번째에 있음 |
| 평균 | 일반적인 입력 분포 | 해시 테이블 평균 조회 |
| 최악 | 가장 불리한 입력 | 퀵 정렬에서 피벗이 계속 한쪽으로 치우침 |
코테에서는 보통 최악 기준으로 통과 가능성을 판단합니다. 문제에서 입력이 정렬되어 있다거나, 값 범위가 작다거나, 그래프가 트리라는 조건을 주면 그 조건을 이용해 더 낮은 복잡도를 고를 수 있습니다.
입력 크기로 판단
시간 제한이 1~2초이고 C# 기준이라면 아래 표를 거친 기준으로 삼을 수 있습니다.
| 입력 크기 | 먼저 의심할 수 있는 복잡도 |
|---|---|
| n ≤ 10 | O(n!), O(2ⁿ)도 가능할 수 있음 |
| n ≤ 20 | 부분집합, 백트래킹, 비트마스크 |
| n ≤ 500 | O(n³)까지 검토 |
| n ≤ 5,000 | O(n²) 가능성 검토 |
| n ≤ 100,000 | O(n log n), O(n) 필요 |
| n ≥ 1,000,000 | O(n) 또는 O(log n) 중심 |
메모리 제한도 같이 봐야 합니다. int[100000][100000] 같은 인접 행렬은 시간보다 메모리에서 먼저 터집니다. n² 배열을 만들기 전에 n의 최댓값을 곱해보는 습관이 필요합니다.
자주 틀리는 점
반복문이 하나라고 무조건 O(n)은 아닙니다. 반복 안에서 Contains, IndexOf, Sort, 문자열 누적 같은 비싼 작업을 호출하면 전체 복잡도가 달라집니다.
List<T>.Contains(x)를 n번 호출하면 보통 O(n²)입니다. 반면 HashSet<T>.Contains(x)를 평균 O(1)로 쓸 수 있으면 전체를 O(n)에 가깝게 줄일 수 있습니다.
참고 링크
2 sources