회원 10만 명 가운데 이름이 같은 두 사람이 있는지 찾는다. 가장 쉬운 방법은 두 사람씩 짝을 지어 모두 비교하는 것이다. 이중 루프 하나면 되고, 짝은 약 50억 개다(n명이면 짝이 n(n − 1)/2개라 n²의 절반쯤이고, 10만² ÷ 2 = 50억이다. 왜 절반인지는 Unit 4에서 본다). 다른 방법도 있다. 회원을 먼저 이름순으로 줄 세우면 같은 이름은 나란히 붙으니, 바로 옆 사람하고만 비교하면 된다. 잘 짠 줄 세우기(정렬)는 비교를 약 n log₂ n번 한다(왜 그런지는 Unit 7에서 본다). n = 10만이면 약 170만 번이다(log₂ 10만 ≈ 17, 10만 × 17). n²과 n log n은 n 뒤에 붙은 것이 다를 뿐인데, 50억과 170만은 약 3,000배 차이다. 이 차이는 어디서 올까?
이 Unit은 입력이 커질 때 일이 늘어나는 모양, 곧 증가 속도(growth rate)를 다룬다. 증가 속도를 적는 법이 Big-O 표기법(Big-O notation)이다. 고른 id가 목록에 있는지 물을 때 배열의 includes는 앞에서부터 한 칸씩 비교하고, Set은 길이와 상관없이 바로 찾는다. 같은 일을 하는 두 코드도 증가 속도가 다를 수 있다는 뜻이다. 여기서는 자주 나오는 증가 속도 일곱 가지를 한꺼번에 견주고, Big-O가 무엇을 버리는지, 루프 모양에서 증가 속도를 어떻게 읽는지 본다.
일곱 가지 증가 속도 견주기
코드가 n에 따라 일을 몇 번 하는지를 식으로 쓰면 대개 아래 일곱 가지 중 하나에 가깝다. log n은 Unit 2의 로그(logarithm)로, n을 1이 될 때까지 반으로 나눈 횟수다. n²은 n × n이고, 2ⁿ은 2를 n번 곱한 거듭제곱(power)이다. n!은 팩토리얼(factorial)이라 읽고, n부터 1까지 모두 곱한 수다. 3! = 3 × 2 × 1 = 6이다. 큰 수는 "약 a × 10ᵏ"으로 적는데, a 뒤에 0이 k개쯤 붙은 수라는 뜻이다.
1초에 10억 번(일 한 번에 1나노초) 계산하는 컴퓨터가 있다. 2ⁿ번 일하는 코드를 n = 100에서 돌리면 얼마나 걸릴까?
선택지와 해설 보기
실험 n이 커지면 일의 양은 얼마나 벌어질까
일곱 가지 증가 속도마다 n일 때 일의 양과, 일 한 번에 1나노초가 걸린다고 칠 때 걸리는 시간을 적었습니다.
| 증가 속도 | 일의 양 | 걸리는 시간 |
|---|---|---|
| 1 | 1 | 1나노초 |
| log n | 3.3 | 3.3나노초 |
| n | 10 | 10나노초 |
| n log n | 33.2 | 33.2나노초 |
| n² | 100 | 100나노초 |
| 2ⁿ | 1, | 1마이크로초 |
| n! | 3, | 3.6밀리초 |
n = 10일 때 걸리는 시간은 n² 100나노초, 2ⁿ 1마이크로초입니다.
- 해볼 것
- n을 20에서 40으로 올려 2ⁿ의 시간이 어떻게 바뀌는지 본다
- n을 1,000,000으로 올려 n log n과 n²의 시간을 견줘 본다
n = 20에서 2ⁿ은 약 1밀리초라 아직 문제가 없다. 그런데 n을 40으로 두 배만 올려도 18분이 넘고, n = 100이면 우주 나이보다 길다. 같은 n = 100에서 n²은 10마이크로초다. n!은 더 빨라서 n = 20에서 이미 약 77년이다. 반대로 n이 100만이어도 n log n은 약 20밀리초, log n은 20나노초다.
같은 내용을 표로 적으면 이렇다. 칸의 수는 일의 횟수다.
| 증가 속도 | n = 10 | n = 100 | n = 1,000 | n = 100만 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| log n | 3.3 | 6.6 | 10 | 20 |
| n | 10 | 100 | 1,000 | 100만 |
| n log n | 33 | 664 | 약 1만 | 약 2,000만 |
| n² | 100 | 1만 | 100만 | 1조 |
| 2ⁿ | 1,024 | 약 1.3 × 10³⁰ | 302자리 수 | 약 30만 자리 수 |
| n! | 3,628,800 | 약 9.3 × 10¹⁵⁷ | 2,568자리 수 | 약 557만 자리 수 |
표를 위에서 아래로 읽으면 세 무리로 나뉜다. 1과 log n은 n이 100만이 돼도 거의 그대로다. n과 n log n은 n과 비슷하게 자란다. n log n은 n에 log n(100만이어도 20)을 곱한 것이라 n보다 많아야 수십 배다. n²부터는 n = 100만에서 1조가 되어, 1나노초에 한 번이어도 16분이 넘는다. 2ⁿ은 n이 60쯤(약 36년), n!은 n이 20쯤(약 77년)만 돼도 현실의 시간을 넘는다. 이 둘이 나오면 n을 아주 작게 두거나, 일부 경우를 건너뛰는 방법이 필요하다.
Big-O가 상수 배와 작은 항을 버리는 이유
실제 코드의 일은 깔끔한 n²이 아니다. 예를 들어 이중 루프의 안쪽 본문이 실행될 때마다 일 3번, 따로 있는 한 겹 루프의 본문이 실행될 때마다 일 100번을 하면 전체는 번이다. "n × n을 3배 한 것에, n의 100배를 더한 것"이라고 읽는다. n = 10이면 300 + 1,000 = 1,300번이다. Big-O는 이것을 O(n²)이라고만 적는다. 100n은 왜 버려도 될까?
일의 양이 3n² + 100n번인 코드가 있다. n = 1,000이면 이 가운데 3n² 항이 전체의 몇 %쯤일까?
선택지와 해설 보기
실험 3n² + 100n에서 3n²의 몫
n을 키우며 두 항 3n²(big)과 100n(small) 가운데 3n²이 전체의 몇 %인지(share) 계산합니다. 막대 전체가 3n² + 100n이고, 두 항이 나눠 가진 길이를 그렸습니다.
const ns = [10, 100, 1000, 10000]for (const n of ns) { const big = 3 * n * n const small = 100 * n const share = big / (big + small) * 100 console.log(`n=${n}: 3n² 몫 ${share.toFixed(1)}%`)}
- ns
- [10, 100, 1000, 10000]
- 해볼 것
- n = 10 ~ 10,000 입력을 끝까지 실행해 본다
n = 10에서는 100n 쪽이 더 커서 3n²이 23.1%밖에 안 된다. n = 100에서 75.0%, 1,000에서 96.8%, 10,000에서 99.7%가 된다. n이 커질수록 n² 항이 전체를 거의 다 차지한다.
3n²을 100n으로 나누면 (n × n × 3) ÷ (n × 100)이고, 위아래의 n 하나를 지우면 3n ÷ 100이다. n이 커질수록 이 비도 같이 커지니, 3n²이 100n의 몇 배인지는 끝없이 늘어난다. 그래서 n이 클 때 전체의 모양은 가장 빨리 자라는 항이 정한다. 작은 항(100n)을 버리는 이유다.
상수 배(3n²의 3)를 버리는 이유는 다르다. 3은 n이 얼마든 늘 3이다. n이 1,000에서 2,000으로 두 배가 되면 3n²도 n²도 똑같이 4배가 된다. Big-O가 묻는 것은 "몇 번인가"가 아니라 "n이 늘면 몇 배가 되나"이고, 그 답에는 상수 배가 영향을 주지 않는다. 같은 이유로 로그의 밑도 버린다. Unit 2에서 봤듯 밑이 300인 로그는 밑이 2인 로그를 늘 약 8.2로 나눈 값, 곧 상수 배만 다르다.
버린다고 없어지는 것은 아니다. 3n²과 n²은 실제로 3배 차이 나고, n이 작으면 100n 항이 더 크다. Big-O는 n이 커질 때의 모양을 견주는 도구이고, 같은 모양끼리 무엇이 빠른지는 측정으로 정한다.
n이 2배면 일은 몇 배일까
증가 속도를 감으로 익히는 가장 쉬운 질문은 "n이 2배가 되면 일은 몇 배?"다. 데이터가 작년의 두 배가 됐을 때 화면이 얼마나 느려질지를 바로 이 질문으로 어림한다.
| 증가 속도 | n이 2배가 되면 | n = 1,000 → 2,000의 예 |
|---|---|---|
| 1 | 그대로 | 1 → 1 |
| log n | 1 늘어남 | 10 → 11 |
| n | 2배 | 1,000 → 2,000 |
| n log n | 2배보다 조금 더 | 약 1만 → 약 2.2만 |
| n² | 4배 | 100만 → 400만 |
| 2ⁿ | 제곱이 됨 | 2¹⁰⁰⁰ → 2²⁰⁰⁰ |
n²이 4배인 이유는 n을 두 번 곱하기 때문이다. (2n) × (2n) = 4 × n × n이다. 2ⁿ은 더 심하다. 이다. "2를 2n번 곱한 것은 2를 n번 곱한 것을 두 번 곱한 것"이라고 읽는다. n = 10이면 2²⁰ = 1,024 × 1,024 = 1,048,576이다. 일이 2배, 4배가 아니라 그 자신을 한 번 더 곱한 만큼 는다. 그래서 2ⁿ은 n이 1 늘기만 해도 일이 두 배다. n이 10 늘면 2¹⁰ = 1,024, 약 1,000배다.
루프 모양에서 증가 속도 읽기
코드를 보고 증가 속도를 읽을 때는 루프의 모양을 본다. 루프 한 겹은 n번, 겹치면 곱한다. 반씩 줄이는 루프는 log n번이다. 네 가지 모양이 하는 일을 세어 보자.
바깥 루프 n번 안에 안쪽 루프 n번이 있는 두 겹 루프가 있다. n이 8에서 16으로 2배가 되면, 안쪽 루프 본문이 실행되는 횟수는 몇 배가 될까?
선택지와 해설 보기
실험 루프 모양 넷이 하는 일의 양
칸 하나가 루프 본문이 한 번 실행되는 것입니다. 반씩 줄이기는 화살표 하나가 한 번입니다. n을 8에서 16으로 바꿔 보세요.
for (i < n)for (i < n) for (j < n)while (k > 1) k = ⌊k / 2⌋for (i < n) { 반씩 }n = 8: 한 겹 8, 두 겹 64, 반씩 3, n × 반씩 24. 네 루프를 한 함수에 나란히 두면 99번이고, 그중 두 겹이 64번이다.
- 해볼 것
- n을 16으로 바꿔 네 루프가 n = 8일 때보다 얼마나 늘었는지 본다
n = 8에서 한 겹은 8, 두 겹은 64, 반씩 줄이기는 3(8 → 4 → 2 → 1), 바깥 n번 안에서 반씩 줄이기(n × 반씩)는 8 × 3 = 24다. n = 16이면 각각 16, 256, 4, 16 × 4 = 64가 된다. 한 겹은 2배, 두 겹은 4배, 반씩 줄이기는 1만 늘었고, n × 반씩은 2배보다 조금 더((16 × 4) ÷ (8 × 3) ≈ 2.7배) 늘었다.
| 루프 모양 | 일의 횟수 | 증가 속도 | 『한입 알고리즘』에서 |
|---|---|---|---|
for (i < n) 한 겹 | n | O(n) | 배열 한 번 훑기 |
for (i < n) 안에 for (j < n) | n × n | O(n²) | 루프 안의 includes |
while (k > 1) k = Math.floor(k / 2) | log n | O(log n) | 이분 탐색(binary search) |
for (i < n) 안에 반씩 줄이는 루프 | n × log n | O(n log n) | 원소마다 이진 힙(binary heap)에 넣기 |
규칙은 둘이다. 루프가 겹치면 각 겹의 횟수를 곱한다. 루프가 나란히 이어지면 더하고, 더한 것 중 가장 빨리 자라는 항만 남긴다. 위 표의 네 루프가 한 함수 안에 나란히 있다면 전체는 n + n² + log n + n log n이고, Big-O로는 가장 큰 O(n²)이다. 루프 변수가 1씩이 아니라 반씩 줄거나 두 배씩 자라면 log n번이다.
O(n²)처럼 적습니다.includes, sort, shift()처럼 한 줄짜리 메서드 안에도 루프가 숨어 있어서, 식을 쓰기 전에 메서드마다 몇 번 일하는지부터 알아야 합니다. 또 버린 상수 배는 실제 시간에는 남아 있습니다.함정 찾기 AI가 쓴 복잡도 설명, 어느 줄이 틀렸을까?
“바깥 루프 n번 안에 안쪽 루프 n번이 있고, 그 뒤에 k를 반씩 줄이는 while이 있는 함수의 시간 복잡도를 설명해 줘.”
의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 3개입니다.
확인 문제 연습
1. 5n + 1000번 일하는 코드의 Big-O는?
2. n이 1,000에서 2,000으로 늘면 O(n²) 코드의 일은 대략 몇 배가 될까?
3. 바깥 루프가 n번 돌고, 그 안에서 매번 크기 n인 정렬된 배열을 이분 탐색(반씩 줄이기)한다. 증가 속도는?
4. 2ⁿ번 일하는 코드에서 n이 10 늘면 일은 대략 몇 배가 될까?
이 Unit이 쓰이는 곳
- 『한입 알고리즘』 0장: 2절 Big-O 표의 "n이 10배가 되면" 열(선형 10배, 제곱 100배)과 4절 데모. 루프 안의
includes가O(n²),Set으로 바꾸면O(n)이다. - 『한입 알고리즘』 5장: 3절 백트래킹(backtracking). 조합 수가 그룹별 선택지 수의 곱이라 그룹이 늘수록 곱으로 커진다. 그룹마다 선택지가 2개면 그룹 n개에서 2ⁿ개다. 4절 가지치기가 이 곱을 줄인다.
- 『한입 알고리즘』 7장: 보너스 "역순 쌍을 O(n log n)에 세기". 이중 루프는
O(n²)이라 n = 10만이면 약 50억 쌍이고, 병합 단계가log n번, 단계마다 원소 전체를 한 번씩 봐서O(n log n)이다. - 『한입 알고리즘』 8장: 4절 "얼마나 아낄까". 상위 k개를 고를 때 전체 정렬
O(n log n)과 크기 k 힙O(n log k)를 견준다.
더 풀어 보기(선택) · 상수가 크면 n²이 이길 때도 있다
알고리즘 A는 100 × n × log₂n번, 알고리즘 B는 n²번 일한다. Big-O로는 A가 O(n log n)이라 낫다. 그런데 n이 작을 때는 누가 덜 일할까? n을 2부터 두 배씩 키울 때 B가 처음으로 A보다 많이 일하는 n을 구하자. 상수가 100이 아니라 1,000이면 그 n은 어떻게 바뀔까?
상수 100 → n = ? 상수 1,000 → n = ?