動的配列のリサイズを例に、ならし解析（amortized analysis）とは何か説明してください。

Question

IT Interview Practice · Accepted Answer

**ならし解析（amortized analysis）** は、個々の操作がときに非常に高コストになる場合でも、**一連の操作にわたる1操作あたりの平均コスト**を測定する手法です。これにより、ときおりO(n)のリサイズが発生するにもかかわらず、動的配列の `append` が「**ならしO(1)**」である理由を説明できます。

## 動的配列の例

動的配列がいっぱいになると、新しい配列（通常は **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
```

| 操作 | 単発の最悪 | ならし |
|---|---|---|
| append（倍々） | O(n) | **O(1)** |

## なぜ倍々なのか（+1ではなく）

**一定量ずつ** 大きくすると、挿入のたびにコピーが発生し、ならしでO(n)になってしまいます。コストを分散させているのは乗算的な成長です。

## なぜ重要なのか

ならし解析は、性能について公平で現実的な姿を示してくれます。これがなければ、すべての `append` やハッシュテーブルへの挿入がO(n)だと誤って恐れてしまうでしょう。

また、**容量は乗算的に増やす** という重要な設計原則を裏付けるものでもあり、これは動的配列、ハッシュテーブル、そしてあらゆる文字列ビルダーの基盤になっています。

動的配列の例

数学的な裏付け

なぜ倍々なのか（+1ではなく）

なぜ重要なのか

関連する質問