앞 글에서 빠르기는 초가 아니라 “데이터가 늘 때 일이 몇 배가 되는가”로 잰다고 했다. 그 물음에 붙은 이름이 빅오다.
초로 재면 안 되는 이유
같은 코드를 내 노트북에서 재면 0.3초, 서버에서 재면 0.05초다. 기계가 바뀌면 숫자가 통째로 달라진다. 그러니 “이 방식은 0.3초짜리다”라는 말은 아무것도 약속하지 못한다.
더 큰 문제가 있다. 100건으로 잰 시간은 100만 건에서 무슨 일이 벌어질지 알려주지 않는다. 100건에서 0.01초였던 두 방식이 100만 건에서 하나는 0.1초, 하나는 40분이 될 수 있다.
우리가 알고 싶은 건 “지금 얼마나 걸리나”가 아니다. **“커지면 어떻게 되나”**다. 그래서 재는 대상을 시간에서 모양으로 바꾼다.
모임에 사람이 두 배로 오면
모임 준비를 맡았다고 하자. 20명이 온다고 했는데 40명으로 늘었다. 할 일마다 부담이 늘어나는 방식이 다르다.
- 공지를 한 번 외친다. 20명이든 40명이든 한 번이다. 사람이 늘어도 안 늘어난다.
- 한 명씩 이름을 부른다. 사람 수만큼이다. 두 배가 오면 두 배.
- 가나다순 명단에서 한 명을 찾는다. 반씩 좁혀 들어가면 두 배가 와도 한 번 더 넘길 뿐이다.
- 모두가 서로 악수한다. 두 배가 오면 네 배가 된다. 사람마다 상대할 사람이 같이 늘어서다.
이 넷이 빅오의 거의 전부다. 나머지는 이 넷의 조합이거나 사이값이다.
여기서 비유가 깨지는 자리를 밝혀둔다. 실제 모임은 사람이 늘면 도와줄 사람도 는다. 하지만 빅오는 일꾼 하나가 순서대로 한다고 놓고 센다. 사람을 더 붙여 나눠 하는 이야기는 빅오가 아니라 병렬 처리 쪽 이야기이고, 둘을 섞으면 “코어를 늘렸는데 왜 그대로냐”에서 길을 잃는다.
늘어나는 모양에 이름을 붙인다
앞의 넷에 이름을 붙이면 그게 빅오다. n은 데이터 개수다.
| 표기 | 모임으로 치면 | 사람이 두 배 오면 |
|---|---|---|
| O(1) | 공지 한 번 외치기 | 그대로 |
| O(log n) | 명단에서 반씩 좁혀 찾기 | 한 번 더 |
| O(n) | 한 명씩 이름 부르기 | 두 배 |
| O(n log n) | 전원을 가나다순으로 줄 세우기 | 두 배보다 조금 더 |
| O(n²) | 모두가 서로 악수 | 네 배 |
왼쪽에서는 다 붙어 있다. 갈리는 건 오른쪽이고, O(n²)는 혼자 천장까지 치솟는다. O(1)만 끝까지 눕는다.
O는 “대략 이 모양으로 늘어난다”는 뜻이고, 괄호 안은 모양이지 시간이 아니다. O(1)이 O(n)보다 늘 빠르다는 뜻도 아니다. 데이터가 충분히 커졌을 때 그렇다는 뜻이다.
상수를 버리는 이유
빅오를 처음 보면 이상한 규칙 하나가 걸린다. O(2n)이라고 안 쓰고 O(n)이라고 쓴다. 상수를 버린다.
버리는 이유는 재는 목적에 있다. 우리가 보는 건 절대값이 아니라 늘어나는 모양이다. 명단을 한 바퀴 도는 것과 두 바퀴 도는 것은, 사람이 두 배로 오면 둘 다 두 배가 된다. 모양이 같다.
낮은 항을 버리는 것도 같다. n² + 100n에서 n이 10,000이면 앞은 1억이고 뒤는 100만이다. 뒤는 1%도 안 되게 묻힌다. 커질수록 큰 항만 남는다.
버려도 되는 건 “커질 때의 모양”을 볼 때뿐이다. 실제로 두 바퀴 도는 코드는 한 바퀴 도는 코드보다 정말로 두 배 느리다. 빅오가 같다고 성능이 같은 게 아니다. 빅오는 “어느 쪽이 지금 빠른가”가 아니라 **“커지면 어느 쪽이 먼저 무너지나”**를 답하는 도구다.
왜 최악을 말하나
상자에서 이메일 하나를 찾을 때, 운이 좋으면 첫 번째에서 나온다. 그럼 O(1)이라고 해도 되지 않나 싶다.
안 된다. 최선은 약속이 될 수 없기 때문이다. 운은 매번 다르지만 “최악이라도 이보다는 낫다”는 매번 지켜진다. 그래서 빅오는 기본적으로 최악을 말한다. 그게 보장이라서다.
다만 최악이 너무 드물어서 평균을 말하는 게 정직한 경우도 있다. 뒤에 볼 해시테이블이 그렇다. 최악은 O(n)인데 실제로는 거의 언제나 O(1)처럼 동작한다. 그때는 최악이 왜 안 일어나는지를 같이 말해야 정직한 설명이 된다.
숨은 반복을 세는 법
세는 법 자체는 간단하다. 반복이 겹치면 곱하고, 나란히 있으면 더한다. 겹친 두 반복은 n × n이라 O(n²)이고, 이어진 두 반복은 n + n이라 O(n)이다.
사람은 두 배가 됐는데 선은 네 배가 넘는다. 각자 상대할 사람이 같이 늘어서다.
진짜 함정은 겹친 반복이 눈에 안 보일 때다.
for (String id : ids) { // n번 돈다
if (blocked.contains(id)) { …} // 이 한 줄이 또 n번 돈다
}contains 한 줄은 반복처럼 안 생겼다. 그런데 blocked가 리스트라면 그 안에서 처음부터 훑는다. 겉보기엔 반복이 하나인데 **실제로는 O(n²)**이다. 목록이 1,000개면 100만 번이다.
고치는 방법은 코드 구조가 아니라 그릇을 바꾸는 것이다. blocked를 Set으로 만들면 contains가 곧장 답해서 전체가 O(n)으로 내려온다. 그게 어떻게 가능한지가 뒤에 볼 해시테이블 이야기다.
실무에서: 빅오가 틀리는 자리
빅오만 보고 판단하면 어긋나는 자리가 있다. 셋을 알아두면 대부분 피한다.
n이 작으면 상수가 이긴다. O(n²)인 단순한 방식이 O(n log n)인 정교한 방식보다 빠른 구간이 실제로 있다. 정렬 라이브러리들이 작은 조각에서는 일부러 단순한 방식으로 갈아타는 이유다. 데이터가 늘 100건이라면 빅오를 따질 자리가 아니다.
진짜 비용은 대개 코드 밖에 있다. 반복문 100만 번이 0.01초인데, DB를 100번 왕복하면 그게 더 걸린다. ORM에서 말하는 N+1이 정확히 이 모양이다. 계산량은 O(n)이지만 그 n이 네트워크 왕복 횟수라 체감이 전혀 다르다. 세는 단위가 무엇인지를 늘 같이 봐야 한다.
같은 O(n)도 어디서 도느냐로 갈린다. 인덱스가 없어 풀스캔이 도는 것과 메모리에서 리스트를 한 바퀴 도는 것은 표기가 같아도 값이 다르다. 앞은 디스크를 두드리고 뒤는 아니다.
여기에 하나 더. OFFSET 방식 페이지네이션은 뒤로 갈수록 느려지는데, 원인이 정확히 이거다. 100번째 페이지를 달라고 하면 DB는 앞의 것들을 세어보고 버린다. 20건을 받는 비용이 아니라 건너뛴 만큼의 비용을 낸다.
정리
- 빠르기는 초가 아니라 늘어나는 모양으로 잰다. 기계가 바뀌어도 모양은 안 바뀐다.
- 모양에 붙인 이름이 빅오다. 그대로(1) · 한 번 더(log n) · 두 배(n) · 네 배(n²).
- 상수와 낮은 항을 버리는 건 모양만 보기 때문이다. 빅오가 같다고 실제 속도가 같은 건 아니다.
- 기본은 최악이다. 최선은 약속이 못 되기 때문이다.
- 가장 흔한 함정은 안 보이는 반복이다. 반복문 안의
contains한 줄이O(n²)을 만든다.
다음 글은 그 모양이 어디서 나오는지를 밑바닥에서 본다. 한자리에 붙여 담은 그릇과 흩어 담고 이은 그릇, 둘의 값이 어떻게 갈리는지다.