시간 복잡도와 빅오 정리: 점근 표기법, 대표 복잡도, 자료구조별 연산 비용
시간 복잡도는 입력 크기 n이 커질 때 연산 횟수가 얼마나 빨리 늘어나는지를 나타낸다. 빅오(O)는 그 증가율의 상한을 표기하며, 상수와 낮은 차수 항은 버리고 가장 빠르게 커지는 항만 남긴다. 실무에서는 보통 최악의 경우를 빅오로 말한다.
1. 왜 실행 시간이 아니라 연산 횟수인가
같은 코드도 CPU, 언어, 입력 데이터에 따라 실행 시간이 다르다. 그래서 알고리즘 자체의 효율은 기계와 무관하게 입력이 커질 때 연산 횟수가 늘어나는 모양으로 비교한다. n이 10일 때는 O(n²)도 빠르지만, n이 100만이 되면 O(n)과 O(n²)의 차이는 수십만 배가 된다.
2. 점근 표기법
| 표기 | 의미 | 비유 |
| O (빅오) | 상한: 이보다 빨리 늘어나지 않는다 | 아무리 오래 걸려도 이 정도 |
| Ω (빅오메가) | 하한: 이보다 느리게 늘어나지 않는다 | 아무리 빨라도 이 정도 |
| Θ (빅세타) | 상한과 하한이 같다 (정확한 증가율) | 딱 이 정도 |
최선·평균·최악은 어떤 입력이냐의 구분이고, O·Ω·Θ는 증가율을 어떻게 표기하느냐의 구분이다. 예를 들어 퀵 정렬은 평균 Θ(n log n), 최악 Θ(n²)다. 면접에서 "빅오는 최악의 경우"라고 말하는 건 흔한 단순화이고, 정확히는 상한 표기다.
3. 계산 규칙
| 규칙 | 예 | 결과 |
| 상수 계수는 버린다 | 3n + 5 | O(n) |
| 낮은 차수 항은 버린다 | n² + 100n | O(n²) |
| 순차 실행은 더한다 | O(n) 반복문 뒤에 O(n²) 반복문 | O(n²) |
| 중첩 실행은 곱한다 | n번 도는 반복문 안에 n번 도는 반복문 | O(n²) |
| 입력이 둘이면 둘 다 남긴다 | 길이 n 배열과 길이 m 배열을 각각 순회 | O(n + m) |
두 번째 반복문은 비교 횟수가 n(n-1)/2라서 정확히는 n²/2 정도지만, 상수 1/2을 버려 O(n²)이다.
4. 대표 복잡도
| 복잡도 | 이름 | 예 | 1초 안에 다룰 수 있는 n (대략) |
| O(1) | 상수 | 배열 인덱스 접근, 해시 조회(평균) | 제한 없음 |
| O(log n) | 로그 | 이진 탐색, 균형 트리 탐색 | 사실상 제한 없음 |
| O(n) | 선형 | 배열 순회, 최댓값 찾기 | 약 1억 |
| O(n log n) | 선형 로그 | 병합 정렬, 힙 정렬, 효율적인 정렬 전반 | 약 수백만 |
| O(n²) | 이차 | 이중 반복문, 버블·삽입 정렬 | 약 1만 |
| O(n³) | 삼차 | 삼중 반복문, 플로이드-워셜 | 약 500 |
| O(2ⁿ) | 지수 | 부분집합 전부 확인 | 약 25 |
| O(n!) | 팩토리얼 | 순열 전부 확인 | 약 10 |
마지막 열은 "단순 연산을 1초에 1억 번 정도 한다"고 가정한 경험칙이다. 코딩 테스트에서 입력 크기를 보고 허용되는 복잡도를 거꾸로 추정할 때 쓴다. n이 10만이면 O(n²)은 100억 번이라 불가능하고, O(n log n) 이하가 필요하다.
5. 로그는 왜 나오나
문제 크기를 매번 절반(또는 일정 비율)으로 줄이면 log n번 만에 1이 된다. n = 1,000,000이어도 log₂n은 약 20이다. 이진 탐색, 균형 이진 트리, B+Tree 인덱스가 빠른 이유다.
6. 자료구조별 연산 비용
| 자료구조 | 인덱스 접근 | 탐색 | 삽입/삭제 | 비고 |
| 배열 (동적 배열) | O(1) | O(n) | 끝: O(1) 분할 상환, 중간: O(n) | 중간 삽입은 뒤 원소를 밀어야 함 |
| 연결 리스트 | O(n) | O(n) | 위치를 알면 O(1) | 위치를 찾는 데 O(n) |
| 해시 테이블 | - | 평균 O(1), 최악 O(n) | 평균 O(1) | 충돌이 몰리면 느려짐 |
| 균형 이진 탐색 트리 | - | O(log n) | O(log n) | 정렬 순서 유지 |
| 이진 힙 | - | O(n) | 삽입·최솟값 삭제 O(log n) | 최솟값 조회는 O(1) |
7. 분할 상환(Amortized) 분석
동적 배열(자바 ArrayList)은 용량이 차면 더 큰 배열을 만들어 전부 복사한다. 이 순간은 O(n)이지만 자주 일어나지 않는다. 용량을 일정 비율로 늘리면(자바 ArrayList는 약 1.5배) n번 추가하는 동안 복사 비용의 합이 O(n)이므로, 한 번 추가의 평균 비용은 O(1)로 본다. 이것을 분할 상환 O(1)이라고 한다.
8. 공간 복잡도
알고리즘이 추가로 쓰는 메모리도 같은 방식으로 표기한다. 입력 배열 외에 크기 n짜리 보조 배열을 만들면 O(n), 변수 몇 개만 쓰면 O(1)이다. 재귀는 호출 깊이만큼 스택을 쓴다는 점을 놓치기 쉽다. 깊이 n까지 들어가는 재귀는 공간 O(n)이고, 너무 깊으면 StackOverflowError가 난다.
9. 실제로 어떻게 적용되나
- 중복 검사: 이중 반복문으로 모든 쌍을 비교하면 O(n²)이다.
HashSet에 넣으면서 이미 있는지 확인하면 O(n)이 된다. 메모리를 조금 더 쓰고 시간을 크게 줄이는 전형적인 교환이다. - 반복문 안의
contains:List.contains는 O(n)이라 n번 반복 안에서 호출하면 O(n²)이다. 조회 대상을 미리Set이나Map으로 바꿔 두면 O(n)이 된다. - 반복문 안의 쿼리: 주문 목록 n건을 돌면서 건마다 상품을 조회하면 쿼리가 n번 나간다. 복잡도 자체는 O(n)이어도 한 번에 드는 상수(네트워크 왕복)가 크다. IN 절이나 조인으로 한 번에 가져온다.
- DB 인덱스: 인덱스가 없으면 테이블 전체를 훑는 O(n), B+Tree 인덱스를 타면 O(log n)으로 찾는다.
10. 면접 질문으로 정리
- Q. 시간 복잡도란? 입력 크기가 커질 때 알고리즘의 연산 횟수가 증가하는 정도를 나타낸 것이다. 실행 환경과 무관하게 알고리즘의 효율을 비교하려고 쓴다.
- Q. 빅오에서 상수를 버리는 이유는? n이 충분히 커지면 증가율이 가장 큰 항이 전체를 지배하기 때문이다. 다만 실제 성능에서는 상수도 중요할 수 있다.
- Q. O(n log n)과 O(n²)의 차이를 체감할 수 있게 설명하면? n이 100만일 때 n log n은 약 2천만, n²은 1조다. 앞의 것은 1초 안에 끝나지만 뒤의 것은 몇 시간이 걸릴 수 있다.
- Q. ArrayList의 add가 O(1)인 이유는? 가끔 일어나는 배열 확장(O(n))을 여러 번의 추가에 나눠 보면 평균이 상수가 되기 때문이다. 이를 분할 상환 O(1)이라고 한다.
- Q. 해시 테이블 조회는 항상 O(1)인가? 평균 O(1)이다. 해시 충돌이 한 버킷에 몰리면 최악 O(n)까지 느려질 수 있다.