빅오 표기법 — 데이터 10배 많아지면 얼마나 느려지나?

빅오 표기법의 핵심은 한 가지입니다: "데이터가 10배 많아지면 얼마나 느려지는가?" 정확한 밀리초가 아니라 증가 패턴을 비교하는 도구입니다.

선형 탐색이 $O(n)$이고 이진 탐색이 $O(\log n)$인 이유도, 해시 테이블 조회가 $O(1)$인 이유도 — 전부 이 한 가지 질문으로 설명됩니다.

n이 커지면 실제로 어떻게 되나?

백만 개의 데이터를 처리한다고 합시다. 알고리즘의 복잡도에 따라 소요 시간이 이렇게 달라집니다:

$O(1)$과 $O(\log n)$은 즉시 끝나고, $O(n^2)$는 12일이 걸립니다. 같은 데이터, 다른 알고리즘 — 이 차이가 빅오를 배우는 이유입니다.

증가 곡선 비교

아래 그래프에서 n이 커질수록 각 복잡도의 연산 횟수가 어떻게 변하는지 보세요. $O(n^2)$가 왜 "폭발한다"고 표현하는지 시각적으로 바로 보입니다.

빅오가 정확히 뜻하는 것

입력 크기 $n$에 대해 알고리즘의 실행 시간이 $T(n)$일 때,

는 "충분히 큰 $n$에서 $T(n)$이 $f(n)$의 상수배를 넘지 않는다"는 뜻입니다.

쉽게 말하면: 상수배와 낮은 차수를 무시하고, 가장 빠르게 커지는 항만 본다.

$T(n) = 3n + 200$이면 → $O(n)$. $3$이나 $200$은 증가 패턴을 바꾸지 않습니다.

자주 보는 5가지 복잡도

• $O(1)$ — 입력이 아무리 커도 연산 횟수가 일정. 해시 테이블 조회, 배열 인덱스 접근.
• $O(\log n)$ — 매번 문제를 절반으로 줄임. 이진 탐색이 대표적. 데이터가 10배 많아져도 3~4단계만 추가.
• $O(n)$ — 데이터를 한 번 훑음. 리스트에서 최댓값 찾기. 데이터 2배 → 시간 2배.
• $O(n \log n)$ — 효율적인 정렬의 한계. 병합 정렬, 힙 정렬. 선형보다 약간 느리지만 여전히 실용적.
• $O(n^2)$ — 이중 반복문. 버블 정렬. 데이터 10배 → 시간 100배. 큰 데이터에선 비현실적.

예제: 왜 이진 탐색은 $O(\log n)$인가?

정렬된 리스트에서 값을 찾을 때, 이진 탐색은 매번 탐색 범위를 절반으로 줄입니다.

100만 개 데이터 → 첫 비교 후 50만 → 25만 → ... → 약 20번 만에 찾습니다.

데이터가 10억 개가 되어도? 약 30번. 이것이 $O(\log n)$의 위력입니다.

반면 선형 탐색은 최악의 경우 100만 번 비교해야 합니다. → $O(n)$.

흔한 실수

"$O(n)$이면 정확히 n번 실행된다" — 아닙니다. $O(n)$은 "n에 비례해서 증가한다"는 뜻이지, 정확히 n단계라는 뜻이 아닙니다. 실제로는 $2n + 5$일 수도, $0.5n$일 수도 있습니다.

"빅오가 작으면 항상 더 빠르다" — 작은 입력에서는 $O(n^2)$가 $O(n \log n)$보다 빠를 수 있습니다. 빅오는 n이 충분히 클 때의 비교입니다.

"빅오만 보면 된다" — 빅오는 증가율만 말합니다. 메모리 사용량, 캐시 친화성, 구현 복잡도도 실제 성능에 큰 영향을 줍니다.