방이 꽉 차면 두 배 넓은 방으로 이사하는 방식이다. 이사는 짐이 많을수록 오래 걸리지만, 방이 커질수록 다음 이사까지 넣을 수 있는 짐도 많아져서 이사가 점점 드물어진다. 그래서 처음부터 끝까지의 수고를 합쳐 짐의 수로 나누면, 짐 하나에 드는 수고는 짐이 아무리 많아져도 일정하다. 단, 두 배처럼 비율로 늘릴 때만 그렇고 한 칸씩 늘리면 넣을 때마다 이사해야 하며, 가끔 한 번이 아주 오래 걸리는 것은 두 배로 늘려도 그대로다.
예시로 보기
배열은 만들 때 칸 수를 정해야 한다. 그런데 원소가 몇 개 들어올지 미리 모를 때가 많다. 칸 수를 코드에 못 박아 두면, 꽉 찼을 때 할 수 있는 일은 오류를 내고 끝내는 것뿐이다.
다른 길이 있다. 칸 수를 변수 capacity에 넣어 두고 1로 시작한다. 꽉 차면 realloc으로 용량을 두 배로 늘린다. 이것이 배열 두 배 늘리기다.
늘릴 때는 이미 든 원소를 새 자리로 옮겨 담아야 한다. 용량 1에서 시작해 아홉 번 넣는 동안 옮겨 담은 수를 센다1.
| 넣는 순서 | 넣기 전 용량 | 꽉 찼는가 | 옮겨 담은 수 | 넣은 뒤 용량 |
|---|---|---|---|---|
| 1 | 1 | 아니다 | 0 | 1 |
| 2 | 1 | 꽉 찼다 | 1 | 2 |
| 3 | 2 | 꽉 찼다 | 2 | 4 |
| 4 | 4 | 아니다 | 0 | 4 |
| 5 | 4 | 꽉 찼다 | 4 | 8 |
| 6, 7, 8 | 8 | 아니다 | 0 | 8 |
| 9 | 8 | 꽉 찼다 | 8 | 16 |
아홉 번째 넣기는 여덟 개를 옮겨야 해서 비싸다. 그래도 아홉 번을 통틀어 옮긴 수는 \(1 + 2 + 4 + 8 = 15\)로, 넣은 횟수의 두 배인 18보다 작다. 비싼 넣기 다음에는 싼 넣기가 그만큼 길게 이어지기 때문이다.
realloc으로 돌려 10만 번 넣는 내내 “옮긴 수 < 2 × 넣은 횟수”인 것, 한 칸씩·열 칸씩 늘릴 때의 옮긴 수, 카드 C1을 C로 컴파일해 실행(ASan·UBSan)해 확인했다 — 08_array-doubling_impl.c. 넣은 횟수 1~100,000 모두에서 아래 식들이 맞는 것은 횟수만 세는 파이썬 코드로 확인했다 — 08_array-doubling_verify.py코드
스택에 쓴 모습이다. 배열의 주소, 지금 용량, 맨 위 원소의 칸 번호를 한 구조체에 묶는다.
typedef struct {
int *data; /* 원소가 든 배열 */
int capacity; /* 지금 배열의 칸 수 */
int top; /* 맨 위 원소의 칸 번호. 비었으면 -1 */
} Stack;
/* 가득 찼을 때 부른다: 용량을 두 배로 늘린다 */
void stack_full(Stack *s)
{
int *bigger = realloc(s->data, (size_t)(2 * s->capacity) * sizeof *s->data);
if (bigger == NULL) { /* 실패하면 옛 배열은 그대로 남아 있다 */
fprintf(stderr, "메모리가 모자란다\n");
free(s->data);
exit(EXIT_FAILURE);
}
s->data = bigger; /* 주소가 바뀌었을 수 있으니 돌려받은 주소를 쓴다 */
s->capacity *= 2;
}
void push(Stack *s, int item)
{
if (s->top >= s->capacity - 1) /* 가득 찼는가 */
stack_full(s);
s->data[++s->top] = item;
}
realloc은 새 자리를 잡고 옛 내용을 옮긴 뒤 옛 자리를 돌려준다. 그래서 늘린 뒤에는 배열의 주소가 달라질 수 있다. 늘리기 전에 배열의 어느 칸을 가리키던 포인터가 있었다면 더는 쓸 수 없다2.
얼마나 드는가
넣기 한 번은 용량만큼 오래 걸릴 수 있다. 꽉 찬 순간에 걸리면 든 원소를 모두 옮겨야 하기 때문이다. 그런데도 \(n\)번을 모두 합치면 \(n\)에 비례하는 시간밖에 들지 않는다.
마지막 용량을 \(2^k\)이라 하자. \(k\)는 용량을 늘린 횟수다. 논증은 세 걸음이다.
- 넣은 횟수는 \(2^{k-1} + 1\) 이상이다. 용량이 \(2^k\)이 되려면 용량 \(2^{k-1}\)이 꽉 찬 뒤에 하나를 더 넣어야 한다.
- 늘리는 데 쓴 시간은 \(\sum_{i=1}^{k} 2^i\)이다. 늘릴 때마다 새 용량만큼 일한다고 넉넉히 잡은 값이다. \(\sum\)는 \(i\)를 1부터 \(k\)까지 바꿔 가며 더하라는 기호다.
- 이 합은 \(O(2^k)\)이다. 2, 4, 8, …처럼 두 배씩 커지는 수를 더하면 합이 마지막 수의 두 배를 넘지 않는다. 정확히는 \(2^{k+1} - 2\)다(등비급수).
1과 3을 이으면, 늘리는 데 쓴 시간은 \(2^{k+1} - 2 < 4 \times 2^{k-1} < 4n\)이다. 넣는 일 자체는 한 번에 한 칸이니 \(n\)이다. 둘을 더해도 \(n\)의 몇 배를 넘지 않는다. 그래서 \(n\)번 넣기 전체가 \(O(n)\)이다1.
표의 아홉 번으로 확인하면 \(k = 4\)이고 \(2^3 + 1 = 9\)번을 넣었다. \(2 + 4 + 8 + 16 = 30\)은 \(4 \times 9 = 36\)보다 작다.
옮겨 담은 원소의 수만 정확히 세면 더 작다. 용량이 1, 2, 4, …, \(2^{k-1}\)일 때 한 번씩 꽉 차므로 다음과 같다1.
\[1 + 2 + 4 + \dots + 2^{k-1} = 2^k - 1 < 2n\]이렇게 여러 번의 비용을 합쳐서 한 번의 비용을 말하는 방법을 분할상환 분석(amortized analysis)이라 부른다1.
한 칸씩 늘리면
꽉 찰 때마다 한 칸만 늘리면 넣을 때마다 꽉 차 있다. 원소가 0개, 1개, 2개, … 든 순간마다 모두 옮겨야 하니 옮긴 수는 \(0 + 1 + 2 + \dots + (n - 1) = \frac{n(n-1)}{2}\)이다. \(n\)이 두 배가 되면 네 배가 된다. 한 번에 열 칸씩 늘려도 열 번에 한 번꼴로 모두 옮기므로 여전히 \(n^2\)에 비례한다1.
| 늘리는 법 | 2,000번 넣을 때 옮긴 수 | 100,000번 넣을 때 옮긴 수 |
|---|---|---|
| 두 배씩 | 2,047 | 131,071 |
| 열 칸씩 | 199,000 | 499,950,000 |
| 한 칸씩 | 1,999,000 | 4,999,950,000 |
갈리는 곳은 “몇 칸을 더하느냐”가 아니라 “지금 용량의 몇 배로 늘리느냐”다. 비율로 늘려야 다음에 꽉 찰 때까지의 간격이 함께 늘어난다.
활용
원소 수를 미리 모르는 배열이면 어디에나 쓴다.
- 스택이 가득 찼을 때 끝내지 않고 늘린다. 스택의 나머지 코드는 배열로 만든 스택에 있다.
- 희소 행렬의 0 아닌 원소 목록은 처음에 크기를 알 수 없다. 기본 용량(예: 10)으로 시작해 필요할 때 늘린다. 그 목록은 희소 행렬의 3원소 표현에서 다룬다. 용량 10에서 시작해 100개를 넣으면 용량은 160이 되고 옮긴 수는 \(10 + 20 + 40 + 80 = 150\)이다1.
- 해시 테이블도 찬 정도가 문턱을 넘으면 두 배쯤 큰 표로 옮긴다. 문턱을 정하는 법은 적재율로 해시 테이블 크기 정하기에 있다.
- 파이썬 리스트의
append가 “평균 \(O(1)\)“인 것도 같은 까닭이다: 시간 복잡도로 방법 고르기
주의. 평균이 일정하다는 것이지 매번 빠르다는 것이 아니다. 65,537번째 넣기는 65,536개를 옮긴다1. 한 번이라도 오래 멈추면 안 되는 프로그램에서는 이 한 번이 문제가 된다.
연결
- 선수: 동적 메모리 할당, 연산 횟수와 단계 수 세기, 등비급수
- 늘릴 일이 아예 없는 구조: 배열과 연결 리스트 비교
확인 문제
C1 용량 1인 빈 배열에 원소를 여섯 번 넣는다. 꽉 찰 때마다 용량을 두 배로 늘린다. 마지막 용량, 늘린 횟수, 옮겨 담은 원소 수의 합은?
답: 용량 8, 늘린 횟수 3, 옮긴 수 \(1 + 2 + 4 = 7\).
이유: 2번째, 3번째, 5번째 넣기에서 꽉 차 있어 각각 1개, 2개, 4개를 옮긴다. 여섯 번째는 용량 8에 다섯 개가 든 상태라 그냥 넣는다.
C2 꽉 찰 때마다 한 칸씩만 늘리면 1,000번 넣는 동안 원소를 몇 번 옮겨 담는가? 두 배씩 늘릴 때와 왜 이렇게 차이가 나는가?
답: 한 칸씩이면 \(0 + 1 + \dots + 999 = 499{,}500\)번, 두 배씩이면 1,023번이다.
이유: 한 칸씩 늘리면 넣을 때마다 꽉 차 있어서 매번 전부 옮긴다. 두 배씩 늘리면 한 번 늘린 뒤 지금 든 만큼을 더 넣을 때까지 옮길 일이 없다. 늘리는 간격이 용량과 함께 커진다.
C3 “마지막 용량이 \(2^k\)이면 넣은 횟수는 \(2^{k-1} + 1\) 이상이다”는 어디서 나오는가? 이 한 줄이 “전체가 \(O(n)\)“이라는 결론에서 맡는 일은 무엇인가?
답: 용량은 꽉 찼을 때만 늘어난다. 용량이 \(2^k\)이 되었다면 용량 \(2^{k-1}\)이 꽉 찬 상태에서 하나를 더 넣은 적이 있다. 그래서 적어도 \(2^{k-1} + 1\)번 넣었다. 이 줄이 있어야 “늘리는 데 쓴 시간은 \(2^k\)에 비례한다”를 “\(n\)에 비례한다”로 바꿀 수 있다. \(2^k < 2n\)이기 때문이다.