ならし解析（amortized analysis） は、個々の操作がときに非常に高コストになる場合でも、一連の操作にわたる1操作あたりの平均コストを測定する手法です。これにより、ときおりO(n)のリサイズが発生するにもかかわらず、動的配列の append が「ならしO(1)」である理由を説明できます。
動的配列がいっぱいになると、新しい配列（通常は 2倍）を確保してすべての要素をコピーします。これはO(n)の処理です。しかし容量が 倍々 になるため、高コストなコピーは指数関数的に稀になります。
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...
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)
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) |
一定量ずつ 大きくすると、挿入のたびにコピーが発生し、ならしでO(n)になってしまいます。コストを分散させているのは乗算的な成長です。
ならし解析は、性能について公平で現実的な姿を示してくれます。これがなければ、すべての append やハッシュテーブルへの挿入がO(n)だと誤って恐れてしまうでしょう。
また、容量は乗算的に増やす という重要な設計原則を裏付けるものでもあり、これは動的配列、ハッシュテーブル、そしてあらゆる文字列ビルダーの基盤になっています。