償却分析 — 操作列にわたる平均コスト

償却分析とは？

償却分析は、最悪ケースの操作列における操作あたりの平均時間を決定します。

動的配列の例

動的配列は満杯時に容量を倍増させます。ほとんどのpushはO(1)ですが、リサイズ時はn要素すべてをコピーします（O(n)）。

n回のpush後のリサイズ総作業量は2n - 1。そのため、**pushあたりの償却コストはO(1)**です。

3つの償却分析手法

手法	アイデア
集約法	n回の操作の総コストを合計し、nで割る
記帳法	安い操作に「クレジット」を割り当て、高い操作の支払いに充てる
ポテンシャル法	データ構造に蓄えられたエネルギーを追跡するポテンシャル関数を定義

重要な理由

償却分析は、時折の高コスト操作があるデータ構造の真のパフォーマンスをより現実的に描写します。「ハッシュテーブルの挿入はO(1)」と言えるのは、リサイズがO(n)であっても償却分析のおかげです。