알고리즘이 입력이 커질 때 얼마나 느려지는지를 나타내는 표기. 기호부터 하나씩 뜯어보자.
n — 입력의 크기
n은 처리해야 할 데이터가 몇 개인가를 나타내는 숫자다. 무엇을 세는지는 문제마다 다르다.
| 상황 | n이 뜻하는 것 |
|---|---|
| 배열에서 값 찾기 | 배열 원소 개수 |
| 회원 목록 정렬 | 회원 수 |
| 그래프 탐색 | 정점 수(보통 V, E는 간선 수) |
| 문자열 비교 | 문자 개수 |
"n이 커진다"는 것은 데이터가 늘어난다는 뜻이다.
O — 증가 추세의 상한
O는 독일어 Ordnung(차수)에서 온 기호로, "이 정도 차수를 넘지 않는다" 는 상한을 뜻한다.
읽을 때는 "빅 오"라고 한다.
O(n)은 "연산 횟수가 n에 비례하는 선을 넘지 않는다"는 의미다.
정확히 몇 번인지가 아니라 어떤 모양으로 늘어나는지를 말한다.
log — 반으로 몇 번 나눌 수 있나
log₂n은 n을 2로 몇 번 나눠야 1이 되는가이다.
n = 8 → 8 → 4 → 2 → 1 3번 → log₂8 = 3
n = 16 → 16 → 8 → 4 → 2 → 1 4번 → log₂16 = 4
n = 1024 → 10번 → log₂1024 = 10
거꾸로 보면 2³ = 8, 2¹⁰ = 1024. 2를 몇 번 곱해야 n이 되는가와 같은 질문이다.
이진 탐색이 O(log n)인 이유가 여기 있다. 매번 후보를 절반씩 버리므로
1024개에서 원하는 값을 찾는 데 최대 10번만 비교하면 된다.
컴퓨터에서 log는 밑이 2인 것이 기본이다. Big-O에서는 밑이 달라도 상수배 차이라 구분하지 않고 그냥
log n이라 쓴다.
숫자로 체감하기
n이 1,000일 때 대략 몇 번 계산하는가.
| 표기 | 이름 | n=1,000 | n이 2배가 되면 |
|---|---|---|---|
O(1) | 상수 | 1번 | 그대로 |
O(log n) | 로그 | 10번 | 1번 늘어남 |
O(n) | 선형 | 1,000번 | 2배 |
O(n log n) | 선형로그 | 10,000번 | 2배 조금 넘게 |
O(n²) | 제곱 | 1,000,000번 | 4배 |
O(2ⁿ) | 지수 | 사실상 불가능 | 제곱으로 |
O(n²)와 O(n log n)의 차이가 1,000,000 대 10,000 — 100배다.
정렬 알고리즘을 고르는 일이 왜 중요한지가 여기서 드러난다.
왜 상수와 계수를 버리는가
3n + 100과 n은 n이 작을 때는 다르지만, n이 커지면 기울기가 같다.
n = 10 → 3n+100 = 130, n = 10 (13배 차이)
n = 10000 → 3n+100 = 30100, n = 10000 (3배 차이)
Big-O의 목적은 규모가 커질 때 무엇이 먼저 무너지는지 보는 것이라 상수는 버린다.
대신 이런 대가가 따른다 — Big-O가 같아도 실제 속도는 다를 수 있다.
n이 작으면 상수가 작은 O(n²)가 상수가 큰 O(n log n)보다 빠른 일이 흔하다.
자료구조별 비교
| 자료구조 | 탐색 | 삽입/삭제 | 이유 |
|---|---|---|---|
| 배열(인덱스) | O(1) | O(n) | 주소 계산으로 즉시 접근 / 밀어내기 필요 |
| 링크드리스트 | O(n) | O(1)* | 앞에서부터 따라가야 함 / 포인터만 바꿈 |
| 해시 테이블 | O(1) 평균 | O(1) 평균 | 키로 위치를 계산 |
| 균형 BST | O(log n) | O(log n) | 매번 절반씩 좁힘 |
* 삽입할 위치의 노드를 이미 들고 있을 때. 찾아가야 하면 O(n)이다.
면접 함정
- "해시는 항상 O(1)" → 평균이
O(1)이다. 충돌이 한 버킷에 몰리면 최악O(n). 자바HashMap은 버킷이 길어지면 트리로 바꿔O(log n)으로 막는다. - "O(n)이 O(n²)보다 항상 빠르다" → 입력이 작으면 상수 차이로 뒤집힌다.
- 평균과 최악을 구분해서 말하라. 퀵 정렬은 평균
O(n log n), 최악O(n²)다. - 공간 복잡도도 함께 언급하면 좋다. 재귀는 호출 스택만큼 메모리를 쓴다
— 깊이가 n이면
O(n)메모리다.