O(1)은 O(N^2) 보다 무조건적으로 빠른가요?
그렇지 않습니다. Big-O는 점근적 표기법으로, 입력 크기 n이 충분히 클 때의 증가율을 나타낼 뿐 절대적인 속도를 보장하지 않습니다.
Big-O가 숨기는 것: 상수항
Big-O는 계산 시 상수를 제거합니다.
실제 수행 시간: 10000 vs 2n²
Big-O 표기: O(1) vs O(n²)
| n | O(1) 실제 연산 수 | O(n²) 실제 연산 수 | 더 빠른 쪽 |
|---|---|---|---|
| 1 | 10,000 | 2 | O(n²) O |
| 10 | 10,000 | 200 | O(n²) O |
| 50 | 10,000 | 5,000 | O(n²) O |
| 71 | 10,000 | 10,082 | 역전 |
| 100 | 10,000 | 20,000 | O(1) O |
n이 작을 때는 상수항이 더 큰 영향을 미칩니다.
Big-O는 "n이 충분히 클 때"의 약속
Big-O의 실제 의미:
"n이 충분히 커지면, O(1)이 O(n²)보다 반드시 빨라진다"
↑
이 전제가 핵심
실무 예시: HashMap vs 이중 루프
// O(1) - 하지만 해시 충돌, 리사이징 등 내부 비용 존재
map.get(key);
// O(n²) - 단순 배열, 캐시 친화적
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ...
n이 매우 작다면 단순 이중 루프가 HashMap보다 빠를 수 있습니다.
정리
Big-O만으로 알고리즘 선택을 결정하면 안 되는 이유입니다.
| 고려 요소 | 설명 |
|---|---|
| 입력 크기 n | n이 작으면 복잡도보다 상수항이 지배 |
| 상수항 크기 | Big-O에서 제거되지만 실제 성능에 영향 |
| 캐시 지역성 | 메모리 접근 패턴이 실제 속도에 큰 영향 |
| 하드웨어 환경 | CPU, 메모리 성능에 따라 결과 상이 |
Big-O는 규모가 커질 때의 경향성을 보는 도구입니다. 항상 실제 환경에서의 벤치마크 측정과 함께 판단해야 합니다.