합 공식: 이중 루프는 왜 n²일까

『한입 알고리즘』 1장에 예산에 딱 맞는 상품 두 개를 고르는 문제가 있다. 가장 쉬운 풀이는 모든 쌍을 한 번씩 비교하는 이중 루프다.

for (let i = 0; i < prices.length; i++) {
  for (let j = i + 1; j < prices.length; j++) {
    if (prices[i] + prices[j] === budget) return [i, j]
  }
}

책은 이 풀이가 "상품 n개에 n(n − 1)/2쌍, O(n²)"이라고 적는다. O(n²)는 입력 n이 커질 때 일이 n²에 비례해 늘어난다는 뜻으로, Big-O 표기법(Big-O notation)으로 적은 것이다(빅오 표기법 노트). 안쪽 루프는 i + 1부터 시작해서 i가 커질수록 점점 짧게 도는데, 왜 n × n과 같은 O(n²)일까? n(n − 1)/2라는 식은 어디서 왔을까? 이 Unit은 1부터 n까지 더한 합을 한 번에 구하는 방법과, 두 배씩 커지는 수의 합이 왜 작게 끝나는지를 본다.

이중 루프의 비교 횟수: 하나씩 세기

1const n = 42let count = 03for (let i = 0; i < n; i++) {4  for (let j = i + 1; j < n; j++) {5    count++6  }7}8console.log(`n = ${n}, 비교 ${count}번`)

n = 4, 비교 6번

비교 횟수를 표로 그리면 모양이 보인다. 행은 i, 열은 j다. 원소 4개의 모든 (i, j) 칸은 4 × 4 = 16칸이고, 그중 코드가 비교하는 칸(✓)은 j > i인 대각선 위쪽뿐이다.

16칸에서 대각선(i = j) 4칸을 빼면 12칸이고, 그 절반인 6칸이 ✓다. n개면 (n × n − n) ÷ 2 = n(n − 1)/2칸이다. n = 4를 넣으면 (16 − 4) ÷ 2 = (4 × 3) ÷ 2 = 6이다. n × n − n은 n을 n번 더한 것에서 한 번 뺀 것, 곧 n을 (n − 1)번 더한 것이라 n(n − 1)이다. 『한입 알고리즘』 1장의 n(n − 1)/2가 바로 이 수다. 안쪽 루프가 짧아져도 비교하는 칸은 여전히 n²의 절반쯤이다.

가우스의 짝짓기: 1 + 2 + … + n을 한 번에

1부터 5까지 더한 값을 하나씩 더하지 않고 구해 보자. 같은 수열을 앞에서부터 한 줄, 뒤에서부터 한 줄 적고 위아래로 짝을 지어 더한다. 수학자 가우스가 어릴 때 1부터 100까지의 합을 1 + 100, 2 + 99, …처럼 양 끝을 짝지어(합이 101인 짝 50개) 금방 구했다는 이야기가 전한다. 두 줄로 적는 것은 그 짝짓기를 눈에 보이게 한 것이다.

1~5처럼 개수가 홀수면 한 줄에서 양 끝을 짝지을 때 가운데 3이 짝 없이 남는다. 줄을 두 번 적으면 모든 수에 짝이 생기고, 마지막에 반으로 나누면 된다. 위아래 합은 모두 6(= 5 + 1)이고 짝이 5개라서 두 줄을 합하면 5 × 6 = 30이다. 같은 수열을 두 번 더했으니 한 줄의 합은 그 절반인 15다. n으로 바꿔 적으면 이렇다.

$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$

말로 읽으면 "1부터 n까지 더한 합은 n 곱하기 (n + 1)을 2로 나눈 값"이다. n = 100이면 100 × 101 ÷ 2 = 5050이다.

이중 루프의 비교 횟수는 1부터 n − 1까지의 합이라서, 식의 n 자리에 n − 1을 넣으면 된다.

$1 + 2 + \cdots + (n-1) = \frac{(n-1)n}{2}$

n = 5면 4 × 5 ÷ 2 = 10으로, 원소 5개 이중 루프의 비교 횟수를 묻던 예측 문제의 답과 같다. n = 1,000이면 999 × 1000 ÷ 2 = 499,500, 약 50만 번이다.

이 식의 위를 풀면 (n − 1) × n = n × n − 1 × n = n² − n이고, 2로 나누면 n²/2 − n/2다. n이 커지면 n²/2에 비해 n/2는 거의 보이지 않는다. n = 1,000에서 n²/2는 50만, n/2는 500이다. Big-O 표기법은 입력이 커질 때 일이 늘어나는 모양만 남기려고 상수 배(1/2)와 작은 쪽(n/2)을 버린다. 그래서 n²/2는 O(n²)이다. n이 두 배가 되면 비교는 약 네 배가 된다.

어느 행에서나 비교 횟수는 n²의 절반쯤이다. 절반이든 전부든 n이 10배가 되면 100배로 자라는 모양은 같다.

시그마 기호와 등차수열: 더하기 루프를 식으로 적기

1 + 2 + … + n처럼 여러 수를 더하라는 식은 시그마(summation) 기호 Σ로 줄여 적는다.

$\sum_{k=1}^{n} k$

읽는 법은 세 군데다. Σ 아래의 k = 1은 시작(k를 1부터), 위의 n은 끝(n까지), 오른쪽의 k는 매번 더할 것이다. "k를 1부터 n까지 바꿔 가며 k를 모두 더한다"고 읽는다. n = 4면 1 + 2 + 3 + 4 = 10이다.

오른쪽이 k가 아니어도 된다. 이중 루프의 비교 횟수는 i마다 안쪽이 n − 1 − i번 도는 것을 i = 0부터 n − 1까지 더한 값이다.

$\sum_{i=0}^{n-1} (n - 1 - i)$

n = 4면 i = 0, 1, 2, 3을 넣어 3 + 2 + 1 + 0 = 6이다. 1절에서 n = 4로 센 비교 횟수와 같다.

1, 2, 3, 4, …처럼 같은 수만큼 일정하게 늘어나는 수의 줄을 등차수열(arithmetic sequence)이라고 한다. 이중 루프의 안쪽 반복 횟수(n − 1, n − 2, …, 1)도 1씩 줄어드는 등차수열이다. 10, 20, 30, …처럼 10씩 늘어나도 등차수열이고, 이때는 10 × (1 + 2 + 3 + …)로 묶어서 같은 짝짓기를 쓴다. 늘어나는 폭이 0이 아닌 등차수열은 n개를 더하면 n²에 비례하는 값이 나온다. 그래서 "반복할 때마다 일이 일정하게 하나씩 늘거나 주는" 코드는 O(n²)다.

두 배씩 늘리는 배열: 1 + 2 + 4 + … + n은 2n보다 작다

이번에는 1, 2, 4, 8, …처럼 같은 수(2)를 곱해 가며 커지는 수를 더해 보자. 이렇게 일정하게 곱해지는 수의 줄을 등비수열(geometric sequence)이라고 한다. 2를 여러 번 곱한 수, 곧 2의 거듭제곱(power)들이다.

『한입 알고리즘』 0장의 보너스 문제에 이 합이 나온다. 동적 배열(dynamic array)은 꽉 차면 두 배 크기의 새 공간을 만들고 원소를 모두 옮겨 담는다. 용량 1에서 시작해 push를 8번 하면 꽉 찰 때마다 1, 2, 4개를 옮겨서 복사는 1 + 2 + 4 = 7번이다. 0장은 이 결과로 push 한 번의 평균이 O(1)이라고 설명한다. 여기서는 "왜 2n보다 작은가"만 본다.

1const n = 642let total = 03let k = 14while (k <= n) {5  total += k6  k *= 27}8console.log(`합 ${total}, 2n = ${2 * n}`)

합 127, 2n = 128

1, 2, 4, …를 n까지 더하는 동안 지금까지 합은 늘 2n보다 작고, 끝까지 더해도 1이 모자란다. 단계마다 합을 적어 보면 규칙이 있다. 1을 더하면 합 1, 2를 더하면 합 3, 4를 더하면 합 7이다. 지금까지 합은 다음에 더할 수보다 늘 1 작다. 새로 더하는 수 하나가 앞의 것을 모두 합친 것보다 크다는 뜻이다.

$1 + 2 + 4 + \cdots + n = 2n - 1$

n이 2의 거듭제곱일 때 성립하고, "두 배씩 커지는 수를 n까지 더하면 2n에서 1이 모자란다"고 읽는다. n = 8이면 1 + 2 + 4 + 8 = 15 = 16 − 1이다.

그림으로 보면 더 분명하다. 길이 2n짜리 막대에 가장 큰 n부터 채운다. n은 막대의 절반이다. 다음 n/2는 남은 칸의 절반, n/4는 또 남은 칸의 절반이다. 조각을 아무리 더해도 오른쪽 끝에는 마지막 조각만큼 빈칸이 남는다.

같은 막대를 n을 1로 놓고 읽으면 n/2는 1/2, n/4는 1/4이니 1 + 1/2 + 1/4 + 1/8 + …이다. 막대 길이는 2이고, 조각을 끝없이 더해도 빈칸이 마지막 조각만큼 남아서 합은 2에 한없이 가까워질 뿐 넘지 않는다.

$1 + \frac{1}{2} + \frac{1}{4} + \cdots < 2$

"1에 그 절반, 또 그 절반을 계속 더해도 2보다 작다"고 읽는다. 1/2 + 1/4 + 1/8을 더하면 7/8이라 1에서 1/8이 모자라고, 1까지 합치면 1.875다.

동적 배열로 돌아가면, 원소 n개를 넣는 동안 복사는 1 + 2 + 4 + … + n/2 = n − 1번이다. 마지막으로 옮기는 묶음은 n개가 아니라 n/2개(용량 n/2가 꽉 찼을 때)라서, 공식의 n 자리에 n/2를 넣으면 2(n/2) − 1 = n − 1이다. n이 2의 거듭제곱이 아니어도 마지막으로 늘린 크기가 2n을 넘지 않으니 복사는 2n보다 적다. 어떤 push 한 번은 원소 n/2개를 옮기느라 오래 걸리지만, n번 전체의 복사가 2n보다 적으니 한 번 평균은 2번이 안 된다. 이렇게 비싼 연산이 드물 때 전체 비용을 연산 횟수로 나눠 평균을 보는 방법을 분할 상환 분석(amortized analysis)이라고 한다.

확인: 복잡도 설명에서 틀린 줄 찾기

검토 기준은 앞 절에 다 나왔다. 합의 식에서 Big-O를 바르게 읽었는가(2절), n이 2배일 때 몇 배인지 맞는가(2절), push 한 번의 비용과 n번의 평균을 구분했는가(4절)를 줄마다 견준다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 0장 Big-O 감각: 함정 찾기에서 스프레드로 배열을 매번 복사하면 1 + 2 + … + n번 복사해 O(n²)이 된다. 보너스에서 두 배씩 늘리는 동적 배열의 복사가 1 + 2 + 4 + … + n/2 = n − 1번이라 push 평균이 O(1)이다.
• 『한입 알고리즘』 1장 해시: 모든 쌍을 비교하면 n(n − 1)/2쌍이다. 버킷 수를 두 배씩 키우는 리해시의 평균 비용이 상수라는 설명도 0장 보너스와 같은 계산이다.
• 『한입 알고리즘』 2장 투 포인터: 원소 n개의 쌍과 연속 구간이 각각 약 n²/2개라서 모두 보면 O(n²)이다.
• 『한입 알고리즘』 7장 정렬: 보너스의 역순 쌍 문제에서 n이 10만이면 모든 쌍이 약 50억 개(10만 × 10만 ÷ 2)다. 7장은 삽입 정렬이 최악 O(n²)이라고 적는데, 이 Unit으로 읽으면 최악의 경우 원소마다 앞쪽을 1, 2, …, n − 1칸씩 미는 횟수의 합이 n(n − 1)/2이기 때문이다.
• 『한입 CS』 8장 데이터베이스: 낙관적 잠금에서 n명이 같은 행을 고치면 재시도가 (n − 1) + (n − 2) + … + 1 = n(n − 1)/2번이다.

n = 100 → 복사 ?번
n = 200 → 복사 ?번