償却計算量の解析手法（会計法・ポテンシャル法）

「たまに重い」を平均でならす

ある操作の計算量を語るとき、普通は最悪計算量（Big-O）を見ます。しかし最悪計算量だけでは損をする場面があります。代表が**動的配列への追加（push）**です。多くの追加は末尾に書くだけで O(1) ですが、容量が一杯になった瞬間だけ新しい大きな領域を確保して全要素をコピーする O(n) が走ります。1回の push の最悪は O(n)。ではこれを n 回繰り返すと O(n²) かというと、実際は O(n) で済みます。

この「個々は最悪 O(n) でも、連続して使えば1回あたり実質 O(1)」を厳密に示すのが償却解析（amortized analysis）です。償却計算量は「一連の m 操作の総コスト ÷ m」、つまり最悪ケースの列に対して保証された平均です。確率や運に依存する平均ではなく、どんな順序で呼んでも成り立つ上界である点が重要です。解析手法は3つあり、同じ結論を別の角度から導きます。

題材：倍々拡張する動的配列

具体例を固定します。容量が一杯のときに push されると、配列は容量を2倍にして既存要素を新領域へコピーします。コピーは要素数に比例するコストです。コストの単位を「要素1個の書き込み＝1」とすると、push 1回のコストは次のようになります。

容量に空きがある push      … コスト 1（末尾に書く）
容量一杯のときの push       … コスト 1 + (それまでの要素数)  ← 2倍に拡張してコピー

push の回数:  1  2  3  4  5  6  7  8  9 ...
要素数:       1  2  3  4  5  6  7  8  9 ...
拡張が起きる:     ✓  ✓     ✓           ✓     ← 容量 1→2→4→8→16...
1回のコスト:  1  2  3  1  5  1  1  1  9 ...   (拡張時は 1+旧要素数)

拡張は容量が 1, 2, 4, 8, ... を超える瞬間、つまり全体で log2(n) 回しか起きません。この構造を3手法でそれぞれ解析します。

手法1：集計法（aggregate method）

集計法は最も素朴で、n 操作の総コストを直接足し上げて n で割るだけです。各操作に別々の値を割り当てず、全体の総和だけを見ます。

n 回の push の総コストは「毎回の末尾書き込み」＋「各拡張時のコピー」に分かれます。末尾書き込みは n 回でちょうど n。コピーは容量が 1, 2, 4, ..., 最大で n 未満の各時点で発生し、そのコストの合計は 1 + 2 + 4 + ... + (n未満の最大の2のべき) です。これは等比級数で、和は最後の項の2倍未満、すなわち 2n 未満に収まります。

総コスト = (末尾書き込み n) + (コピー 1+2+4+...+ < 2n)
        < n + 2n = 3n = O(n)

償却コスト = O(n) / n = O(1)

ポイントは等比級数の和が初項や最終項の定数倍に収まることです。コピーは回を追うごとに重くなりますが、重い拡張ほど頻度が低い（間隔が倍々に空く）ので、総和は線形で抑えられます。集計法は総和さえ評価できれば一発ですが、操作の種類が複数あって絡み合うと総和を直接数えにくくなります。そこで次の2手法が要ります。

手法2：会計法（accounting method）

会計法（banker's method とも）は、各操作に実コストとは別の「課金額（amortized cost）」を割り当て、課金が実コストを上回った差額を前払いの貯金（credit）としてデータ構造に蓄えるという考え方です。後で高コストの操作が来たら、貯めた貯金で支払います。

ルールは1つ。どの時点でも貯金が負になってはいけない。これが守られていれば「課金額の総和 ≥ 実コストの総和」が常に成り立ち、課金額が償却コストの正しい上界になります。

動的配列では、各 push に課金額 3を割り当てます。内訳は次のように解釈します。

なぜ3で足りるかを直感で言うと、容量が2倍になる直前には「前回の拡張後に追加された新しい要素」が配列の半分を占めています。拡張で全要素をコピーする際、新しい半分は自分の貯金（2個目のクレジット）で払えます。残り半分の古い要素は、新しい半分が払う3個目のクレジットで肩代わりできます。こうしてどの拡張時にも貯金が枯れず、各 push の課金 3 = O(1) が償却コストになります。

手法3：ポテンシャル法（potential method）

ポテンシャル法は会計法を一般化・形式化したものです。貯金を要素ごとに配るのではなく、データ構造の状態 D 全体に対して1つの数値「ポテンシャル」Phi(D) を定義します。Phi は構造に蓄えられたエネルギー（＝将来の高コストに備えた貯金の総額）だと思えます。

i 番目の操作の償却コストを次で定義します（記号 c_i は実コスト、Phi_i は操作後のポテンシャル）。

償却コスト_i = c_i + Phi_i - Phi_{i-1}
            = 実コスト + ポテンシャルの増分

実コストが安いのにポテンシャルを増やす操作は、その差額を償却コストに上乗せして「貯金」します。逆に実コストが高い操作は、ポテンシャルを大きく減らすことで増分が負になり、その分が実コストを相殺します。n 操作の償却コストを総和すると中間の Phi が打ち消し合い（telescoping）、次が得られます。

Σ 償却コスト_i = Σ c_i + Phi_n - Phi_0

Phi_0 = 0 かつ常に Phi_i >= 0（ポテンシャルが初期値を下回らない）ように Phi を選べば、Σ 償却コスト ≥ Σ 実コスト となり、償却コストが総実コストの上界を与えます。

動的配列では Phi = 2 * (要素数) - (容量) と置くのが定番です。拡張直後は要素数が容量のちょうど半分なので Phi は 0 付近、容量一杯の直前では要素数＝容量で Phi が容量と等しい最大値、つまり次の重いコピーをちょうど賄えるだけのエネルギーが溜まっている状態になります。

拡張時は容量が n から 2n に増えるため -(容量) の項が一気に効き、ポテンシャルの減少が n 回分のコピー実コストを打ち消します。結果、どちらの場合も償却コストは定数 O(1) に収まります。

縮小と「揺さぶり」への注意

償却 O(1) が成り立つのは拡張のしきい値と縮小のしきい値を分けた場合です。素朴に「半分埋まったら半分に縮小、一杯なら2倍に拡張」とすると、容量の境界ちょうどで push と pop を交互に呼ばれたとき、毎回フルコピーが走り償却 O(n) に劣化します。

これを防ぐ定石は、縮小を 1/4 まで減ったときに半分にすることです。拡張点（一杯）と縮小点（1/4）の間に十分な余白を空けることで、1回の高コスト操作の後、次の高コストまでに必ず Θ(n) 回の安い操作が挟まり、ポテンシャルを貯め直す時間が確保されます。境界の余白こそが償却保証の生命線です。

まとめ

償却解析は「個々の最悪コストを足すと過大評価になる」場面で、一連の操作にならした正しいコストを与える道具です。集計法は総和を直接、会計法は前払いの貯金、ポテンシャル法は状態のエネルギー関数で、いずれも「たまの高コストを、それを準備した多数の安い操作へ薄く分散する」という同じ現象を別表現で捉えます。動的配列の倍々拡張はその典型で、どの手法でも償却 O(1) に着地します。この見方はハッシュ表のリハッシュや union-find、各種データ構造の更新コスト評価に共通して効き、ソートのような単発アルゴリズムの最悪解析とは別軸の、操作列としての性能を正しく見積もるための基礎になります。