시간복잡도와 Big-O: 코드에서 읽는 법과 한계
들어가며
두 목록의 공통 원소를 찾는 코드가 있습니다. 데이터가 10배 늘었더니 실행 시간은 100배가 됐습니다. 코드는 그대로인데 왜 이렇게 늘었을까요?
이번 글에서는 이런 변화를 미리 읽게 해 주는 시간복잡도와 Big-O 표기를 정리합니다. 코드에서 복잡도를 읽는 방법, 자주 만나는 복잡도, 그리고 Big-O 가 말해 주지 않는 것까지 다룹니다.
1. Big-O 는 증가 추세를 적는 표기
시간복잡도는 입력 크기 n 이 커질 때 연산 횟수가 어떻게 늘어나는지를 나타냅니다. 실제 시간이 아니라 늘어나는 모양입니다. 연산이 3n + 5 번이라면 n 이 커질수록 3 과 5 의 영향은 작아지므로 O(n) 으로 적습니다.
Big-O는 손님이 늘 때 줄이 얼마나 빨리 길어지는지 나타내는 표시예요.
| 복잡도 | 대표 예 | n = 10 | n = 1천 | n = 100만 |
|---|---|---|---|---|
| O(1)상수 | 해시 조회 | 1 | 1 | 1 |
| O(log n)로그 | 이진 탐색 | 약 3 | 약 10 | 약 20 |
| O(n)선형 | 전체 순회 | 10 | 1천 | 100만 |
| O(n log n)선형 로그 | 정렬 | 약 33 | 약 1만 | 약 2천만 |
| O(n²)제곱 | 이중 루프 | 100 | 100만 | 1조 |
표에서 보듯 n 이 작을 때는 차이가 크지 않지만, 100만 개가 되면 O(n log n) 과 O(n²) 은 몇만 배 차이가 납니다.
메모리도 같은 방식으로 표기하며, 이것을 공간복잡도라고 부릅니다.
2. 코드에서 읽는 법
반복문의 위치만 봐도 대부분 읽을 수 있습니다. 나란히 있으면 더하고, 안에 있으면 곱합니다.
# O(n): 한 번 훑기
for x in a: ...
# O(n + m): 나란히 두 번, 더하기
for x in a: ...
for y in b: ...
# O(n²): 안에서 또 훑기, 곱하기
for x in a:
for y in a: ...입력이 둘이면 문자도 나눕니다. 한 목록을 훑은 뒤 다른 목록을 훑으면 O(2n) 이 아니라 O(n + m) 입니다. 마지막으로 상수와 작은 항을 빼서, n² + n 은 O(n²) 으로 적습니다.
여기서 놓치기 쉬운 것이 호출 안에 숨은 반복입니다. 파이썬에서 리스트의 x in b 와 b.pop(0) 은 O(n) 이고, sorted(a) 는 O(n log n) 입니다. 반복문 한 겹처럼 보여도 그 안에서 이런 호출을 하면 복잡도가 곱해집니다.
3. O(log n): 절반씩 줄이기
이진 탐색은 비교할 때마다 후보를 절반으로 줄입니다. 8개 중 7을 찾으면 8 → 4 → 2 → 1 로 줄어 세 번이면 끝납니다.
이진 탐색은 두꺼운 사전을 가운데서 펼쳐 앞뒤를 고르는 일을 반복하는 거예요.
횟수는 n 을 1이 될 때까지 반으로 나눈 수입니다. 그래서 100만 개도 약 20번이면 찾습니다. 단, 데이터가 정렬돼 있어야 합니다. DB 의 B-tree 인덱스도 같은 원리로 O(log n) 탐색을 합니다.
4. 해시로 바꾸면 달라지는 것
처음의 공통 원소 문제로 돌아가 보겠습니다. 리스트의 in 은 앞에서부터 전부 훑으므로 전체는 O(n × m) 입니다. 데이터가 양쪽 10배로 늘면 100배가 되는 이유입니다.
# 나쁨: O(n × m). b 는 list
common = [x for x in a if x in b]
# 좋음: O(n + m). 메모리 O(m) 추가
b_set = set(b)
common = [x for x in a if x in b_set]set 조회는 책을 처음부터 넘기는 대신 색인을 만들어 두고 바로 펼치는 일이에요.
- a 를 1만 번 순회
- 매번 b 를 전부 훑기× 1만
- 추가 메모리 없음
- b 로 집합 만들기1만 번
- a 를 1만 번 순회
- 메모리 O(m) 추가
집합의 조회는 평균 O(1) 이라 연산 횟수가 크게 줄어듭니다. 대신 해시 집합을 만들 메모리를 더 씁니다. 시간과 메모리를 맞바꾸는 대표적인 예입니다.
5. 평균, 최악, 분할 상환
같은 연산도 경우에 따라 복잡도가 다릅니다. 해시 조회는 평균 O(1) 이지만 충돌이 한 칸에 몰리면 최악에는 O(n) 입니다.
파이썬 list.append 는 평소 빈칸에 넣기만 하므로 O(1) 입니다. 칸이 차면 더 큰 배열로 옮기느라 그 한 번은 O(n) 이지만, 드물게 일어나므로 나눠 보면 평균 O(1) 입니다. 이것을 분할 상환 분석이라고 합니다.
6. Big-O 가 말해 주지 않는 것
Big-O 는 상수를 뺀 표기라 실제 시간을 알려 주지 않습니다. n 이 작으면 O(n²) 이 O(n log n) 보다 빠를 수 있습니다. 파이썬 내장 정렬인 Timsort 가 짧은 구간에 삽입 정렬을 쓰는 것도 이 때문입니다.
메모리 캐시 효과나 네트워크 왕복처럼 표기에 없는 비용이 지배할 때도 많습니다. 그래서 복잡도로 규모 예측을 하고, 결론은 실측으로 확인합니다.
import cProfile
cProfile.run("find_common(a, b)", sort="cumulative")헷갈리기 쉬운 점
- 반복문이 두 개면 O(n²) 이라는 오해. 나란히 있으면 더하기입니다. 안에 들어 있어야 곱하기가 됩니다.
- O(n) 이 O(n²) 보다 항상 빠르다는 오해. Big-O 는 커질 때의 추세만 말합니다. n 이 작으면 상수가 작은 쪽이 빠를 수 있습니다.
- Big-O 는 최악의 경우만 뜻한다는 오해. Big-O 는 상한 표기이고, 평균과 최악은 따로 말합니다. 해시 조회를 평균 O(1) 이라고 하는 것이 그 예입니다.
면접에서 자주 받는 질문
이진 탐색은 왜 O(log n) 인가요?
비교할 때마다 후보가 절반으로 줄기 때문입니다. 횟수는 n 을 1이 될 때까지 반으로 나눈 수이고, 100만 개도 약 20번이면 끝납니다. 데이터가 정렬돼 있어야 합니다.
파이썬 dict 조회는 항상 O(1) 인가요?
평균이 O(1) 이고 충돌이 몰리면 최악은 O(n) 입니다. 파이썬은 문자열 해시를 프로세스마다 무작위로 바꿔 의도적인 충돌 공격을 어렵게 합니다.
인덱스 조회와 풀스캔을 Big-O 로 비교하면요?
B-tree 탐색은 O(log n), 풀스캔은 O(n) 입니다. 다만 조건에 걸리는 행이 많으면 행마다 테이블을 읽는 비용이 커져 풀스캔이 더 빠를 수 있으므로, 플래너는 예상 비용으로 고릅니다.
정리
- Big-O 는 입력이 커질 때 연산 횟수가 늘어나는 모양을 상수와 작은 항을 빼고 적은 표기입니다.
- 코드에서는 나란히 있으면 더하고 안에 있으면 곱하며, 호출 안에 숨은 반복도 함께 셉니다.
- 복잡도로 규모를 예측하되 실제 시간은 실측으로 확인합니다.
나란히는 더하기, 안에 있으면 곱하기. 이 한 줄이면 대부분의 코드를 읽을 수 있습니다.