입력이 얼마나 큰지는 코드를 쓰기 전에 이미 정해져 있고, 그 크기에 따라 쓸 수 있는 방법과 쓸 수 없는 방법이 갈립니다.
복잡도는 시간을 재는 것이 아닙니다
시간 복잡도(time complexity) 는 코드가 몇 초 걸리는지 재는 도구가 아니라, 입력이 커질 때 연산 횟수가 어떤 모양으로 늘어나는지를 나타내는 도구입니다.
같은 코드도 기계에 따라 실행 시간이 다릅니다. 언어에 따라, 컴파일러 최적화에 따라, 캐시 적중률에 따라 배 단위로 흔들립니다. 그래서 절대 시간은 비교 기준이 되기 어렵습니다.
반면 증가하는 모양은 기계와 무관합니다. 입력이 두 배가 될 때 연산이 두 배 늘어나는 코드와 네 배 늘어나는 코드는 어떤 기계에서 돌려도 그 관계를 유지합니다. 점근 표기법(asymptotic notation) 은 이 관계를 적는 방법입니다. 입력 N이 커질 때 연산 횟수가 N에 비례하면 O(N), N의 제곱에 비례하면 O(N²)처럼, 가장 빠르게 커지는 항 하나만 남겨 증가 속도를 나타냅니다.
배열에 같은 값이 두 번 있는지 이중 반복문으로 확인하는 함수를 예로 듭니다.
function hasDuplicate(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true; // 비교 한 번
}
}
return false;
}원소가 N개면 비교는 최대 N(N-1)/2번입니다. N이 10이면 45번, 100이면 4,950번, 1,000이면 499,500번이라 N이 열 배가 될 때 비교는 백 배 가까이 늘어납니다. 그래서 이 함수의 시간 복잡도는 O(N²)입니다.
같은 이유로 O(2N)과 O(N)을 구분하지 않습니다. 상수 2는 기계가 바뀌면 달라지는 값이고, 우리가 알고 싶은 건 모양이기 때문입니다.
상수를 버려서 얻는 것과 잃는 것
위 함수의 비교 횟수 N(N-1)/2를 풀면 N²/2 - N/2입니다. 여기서 계수 1/2과 낮은 차수 항 N/2를 버립니다. 반복문 안에서 연산을 세 번 하든 다섯 번 하든 3N, 5N이 아니라 N으로 보는 것도 같은 원리입니다. 이렇게 상수를 버리면 판단이 빨라집니다. 반복문 하나면 O(N), 중첩 반복문이면 O(N²)이라고 즉시 말할 수 있습니다. 코드를 읽자마자 규모를 가늠할 수 있게 됩니다.
잃는 것도 있습니다. N이 작을 때는 상수가 지배합니다. 원소 열 개짜리 배열에서는 O(N²) 삽입 정렬이 O(N log N) 병합 정렬보다 빠른 경우가 흔합니다. 병합 정렬은 재귀 호출과 추가 배열 할당이라는 상수 비용을 치르는데, N이 작으면 그 비용을 회수할 만큼 이득이 나지 않습니다.
실제 정렬 라이브러리가 작은 구간에서 삽입 정렬로 갈아타는 이유가 여기에 있습니다. 점근 표기법은 큰 입력에서의 판단 도구이고, 작은 입력에서는 실측이 필요합니다.
1초에 1억 번이라는 기준선
경험적으로 봤을 때, 요즘 환경에서 단순 연산은 보통 1초에 1억 번쯤 처리된다고 합니다.
정확한 수치는 아닙니다. 언어와 연산 종류에 따라 크게 달라지고, 자바스크립트처럼 런타임 계층이 두꺼운 환경에서는 더 보수적으로 잡아야 합니다. 그래도 자릿수 감각을 잡는 기준으로는 씁니다.
이 기준이 있으면 역산이 가능해집니다. 입력 N이 주어졌을 때 1억을 넘지 않는 복잡도가 무엇인지 계산하면 됩니다.
표로 정리하면 이렇습니다.
| 입력 크기 N | 허용되는 복잡도 | 대표적인 접근 |
|---|---|---|
| 10 이하 | O(N!) | 모든 순열 나열 |
| 20 이하 | O(2N) | 부분집합 전부 확인, 비트마스킹 |
| 500 이하 | O(N³) | 삼중 반복문, 전체 쌍 최단거리 |
| 5,000 이하 | O(N²) | 이중 반복문, 모든 쌍 비교 |
| 100,000 이하 | O(N log N) | 정렬, 이분탐색 반복 |
| 1,000,000 이하 | O(N) | 한 번 훑기, 투 포인터 |
| 그 이상 | O(log N), O(1) | 수식 계산, 이분탐색 단독 |
입력이 십만 개인데 이중 반복문을 쓰고 있다면, 코드가 아니라 접근이 잘못된 겁니다. 최적화로 메울 수 있는 간격이 아닙니다.
최선과 평균과 최악은 서로 다른 질문입니다
같은 자료구조도 상황에 따라 다른 답을 냅니다.
해시 테이블 조회는 평균 O(1)입니다. 그런데 모든 키가 같은 버킷으로 몰리면 O(N)이 됩니다. 퀵 정렬은 평균 O(N log N)이지만 이미 정렬된 입력에서 피벗을 잘못 고르면 O(N²)이 됩니다.
어느 쪽을 기준으로 판단해야 할지는 무엇을 보장해야 하느냐에 달려 있습니다.
- 모든 사용자 요청에 응답 시간을 보장해야 하면 최악을 봅니다
- 대량 배치를 전체적으로 빨리 끝내야 하면 평균을 봅니다
- 입력의 성격을 통제할 수 있으면 최악 조건을 피하는 쪽으로 설계합니다
상각 분석(amortized analysis) 이라는 관점도 있습니다. 동적 배열에 원소를 추가할 때 대부분은 O(1)이지만, 용량이 꽉 차는 순간에는 전체를 새 공간으로 복사하느라 O(N)이 듭니다. 이 비싼 연산이 드물게 발생하므로, 여러 번의 추가에 걸쳐 나누면 평균 O(1)로 볼 수 있습니다. 개별 연산의 최악과 연산 묶음의 평균이 다르다는 뜻입니다.
공간도 같이 셉니다
공간 복잡도(space complexity) 를 보지 않고 시간만 보다가 메모리에서 막히는 경우가 있습니다.
2차원 배열로 동적 계획법 테이블을 만들 때가 대표적입니다. N이 10,000이고 M이 10,000이면 칸이 1억 개입니다. 숫자 하나에 8바이트만 잡아도 800MB입니다. 시간은 O(N × M)으로 통과하는데 메모리에서 막힙니다.
이전 행만 참조하는 점화식이라면 전체 테이블을 들고 있을 이유가 없습니다. 두 행만 번갈아 쓰면 공간이 O(N × M)에서 O(M)으로 줄어듭니다.
// 전체 테이블: 공간 O(n * m)
const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
// 두 행만 유지: 공간 O(m)
let prev = new Array(m + 1).fill(0);
let curr = new Array(m + 1).fill(0);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
[prev, curr] = [curr, prev]; // 두 행을 교체
}점화식이 바로 위 행만 참조한다면 이 교체가 항상 성립합니다. 시간은 그대로이고 공간만 줄어듭니다.
코드를 쓰기 전에 하는 계산
정리하면 입력 크기를 먼저 확인하고, 위 표에서 허용 복잡도를 찾고, 그 복잡도 안에서 가능한 접근을 고른 다음에 코드를 씁니다.
거꾸로 하면 비용이 큽니다. 구현을 끝내고 나서 복잡도가 맞지 않는다는 걸 알면 접근 자체를 다시 잡고 로직을 새로 짜야 합니다.
참고 자료
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
다음 편 예고
가장 많이 쓰는 두 자료구조를 봅니다. 해시 테이블은 왜 평균 O(1)인데 최악이 O(N)인지, 배열 앞에 값을 넣는 코드는 왜 조용히 느려지는지 다룹니다.