什么是摊销分析，以动态数组重新调整大小为例？

Question

Accepted Answer

**摊销分析** 测量**序列中每个操作的平均成本**，即使单个操作偶尔会花费更多。它解释了为什么动态数组的 `append` 是"**O(1) 摊销**"，尽管偶尔会发生 O(n) 的重新调整大小。

## 动态数组示例

当动态数组满时，它会分配一个新数组（通常**2倍**），并复制所有元素——这是一个 O(n) 步骤。但由于容量**加倍**，昂贵的复制操作变得指数级地罕见。

```text
Appending into a doubling array (cap shown):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- copies at 1,2,4,8,16...
```

## 数学推导

```text
To insert n elements, total copy work =
  1 + 2 + 4 + ... + n  ≈  2n   (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # almost always O(1); rarely O(n) during a resize
```

| Operation | Worst single | Amortized |
|---|---|---|
| append (doubling) | O(n) | **O(1)** |

## 为什么是加倍（不是加1）

如果容量增长**固定量**，每次插入都会触发一次复制，导致 O(n) 摊销时间。乘法增长才能真正分散这个成本。

## 为什么这很重要

摊销分析提供了一个公平、现实的性能观点——没有它，你会错误地认为每个 `append` 或哈希表插入都是 O(n)。

它还论证了一个关键的设计原则：**按倍数增长容量**，这是动态数组、哈希表和字符串构造器等到处都采用的原则。