dynamic array 리사이징을 예로 들어, amortized 분석이란 무엇인가요?

Question

Accepted Answer

**Amortized 분석(분할 상환 분석)**은 개별 연산이 가끔 훨씬 더 비쌀 때조차도, **연산 시퀀스 전체에 걸친 연산당 평균 비용**을 측정합니다. 이는 dynamic array의 `append`가 가끔 O(n) 리사이즈가 있음에도 왜 "**O(1) amortized**"인지를 설명합니다.

## dynamic array 예시

dynamic array가 가득 차면 새 array(보통 **2배**)를 할당하고 모든 원소를 복사합니다. O(n) 단계죠. 하지만 용량이 **두 배**가 되기 때문에 비싼 복사는 기하급수적으로 드물어집니다.

```text
배가 array에 append (용량 표시):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- 1,2,4,8,16... 에서 복사
```

## 수학

```text
n개의 원소를 삽입하려면, 총 복사 작업 =
  1 + 2 + 4 + ... + n  ≈  2n   (등비급수)
n번 삽입의 총 비용 = O(n)
삽입당 amortized 비용 = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # 거의 항상 O(1); 리사이즈 동안 드물게 O(n)
```

| 연산 | 최악의 단일 | Amortized |
|---|---|---|
| append(배가) | O(n) | **O(1)** |

## 왜 +1이 아니라 배가인가

**상수량**만큼 늘리면 매 삽입마다 복사가 발생하여 O(n) amortized가 됩니다. 비용을 분산시키는 것은 곱셈적 성장입니다.

## 왜 중요한가

amortized 분석은 공정하고 현실적인 성능 그림을 제공합니다. 이것이 없으면 모든 `append`나 hash table 삽입이 O(n)이라고 잘못 두려워하게 됩니다.

또한 핵심 설계 규칙을 정당화합니다. **용량을 곱셈적으로 늘려라**. 이는 어디서나 dynamic array, hash table, 문자열 빌더의 기반이 됩니다.