評価するのは許された操作列の総費用
償却解析は、一回の操作だけでなく、ある初期状態から行う操作列全体の費用を評価する方法です。高価な操作があっても、それを繰り返すために多くの安い操作が必要なら、全体の上界を小さくできます。操作数mの列について総費用がC・m以下と示せれば、その範囲で一操作当たりの償却費用はO(1)です。ただし、許す操作や初期状態は証明の一部です。追加だけの列で得た評価を、途中への挿入や任意の削除を含む列へ自動的に広げることはできません。何を一回の費用として数えるかも、要素のコピーやスタック操作など、対象に合わせて先に定めます。
期待値の平均とは別の議論をする
入力を確率分布から選んだときの平均や、乱数を使うアルゴリズムの期待値は、確率に関する仮定を使います。償却解析は、通常、許されたどの操作列にも適用できる総費用の上界を示す議論です。頻度の高い入力だけを測って平均時間を出すこととも異なります。例えば倍増配列では、利用者が拡張の直前を狙って追加しても、空からそこへ到達するまでに積み上がった操作を含めれば評価が成り立ちます。どんな一回でも安いわけではありませんが、最悪の操作列全体に対する制約を示せる点が重要です。確率的な解析と償却解析を同時に使う設計もあるため、名称を排他的に捉える必要はありません。
容量倍増のコピーを八回の追加で数える
初期容量1の空配列に8個の要素を末尾追加し、満杯のとき容量を2倍にするとします。要素を保存する通常の書き込みは8回です。拡張時に移す既存要素は、容量1から2で1個、2から4で2個、4から8で4個なので、合計7個です。このモデルの費用を通常の書き込みとコピーの和で数えると15です。第5要素を入れる一回は、4個のコピーと新要素の書き込みで5となり、定数の小さい操作とはいえません。それでも8回全体は15で済みます。各挿入を個別に最悪O(n)として8回分を足すだけでは、実際には連続して起きない拡張まで繰り返すように数えてしまいます。
幾何級数を使って一般のnへ広げる
n個を追加した場合も、コピー数は1+2+4+…という倍増の列で数えられます。最後にコピーした要素数はn未満であり、この総和は2n未満に抑えられます。通常のn回の書き込みを加えても、総費用は3n未満という線形の上界を得られます。これは説明用の単位費用モデルであり、実時間を3nナノ秒と予測する式ではありません。要素の移動に複雑なコンストラクタや参照カウント処理が必要なら、その一要素当たりの費用も考えます。容量増加率を固定しても、その率が1へ近づくとコピーにかかる定数は大きくなるため、メモリの余裕と移動費用の両方を比較します。
蓄えを使うなら初期値と残高を確認する
会計法では、安い操作のときに余分の仮想的な費用を課し、後の高い操作に備えて蓄えを持たせます。ポテンシャル法なら、実費用に状態のポテンシャルの変化を足したものを償却費用として定義します。操作列で変化を足すと途中の項が相殺され、最後と最初のポテンシャルだけが残ります。将来の費用を勝手に消してよいわけではありません。初期ポテンシャルが有界で、最終ポテンシャルが必要な下界を持つことを確認します。最初から大量のデータが入った状態を無料として始めるなら、その初期の仕事や蓄えを別に扱わなければ、空からの証明と同じ結論にはなりません。
二つのスタックでは各要素を数える
入力スタックへ追加し、出力スタックが空のときだけ入力側を全部移して逆順にするキューを考えます。A、B、Cを追加した後の最初の取り出しでは、3要素の移動が起こり得ます。しかし各要素は入力側へ一度積まれ、そこから一度取り出されて出力側へ積まれ、最後に一度取り出されるだけです。基本のスタック操作を定数費用とすれば、各要素に課す仕事は定数回なので、空からの任意の追加・取り出しの列の費用は操作数に比例します。出力側にまだ要素があるのに毎回移し直す実装や、要素を両方向へ繰り返し戻す実装には、この数え方をそのまま使えません。
縮小を加えると往復が起きる
容量を増やすだけの証明へ、削除時の縮小を追加するときには注意が必要です。例えば満杯で倍増した直後に、使用率が半分程度になったという理由ですぐ半減すると、追加と削除の繰り返しで大きな配列を何度も移す恐れがあります。拡張するしきい値と縮小するしきい値を離し、ある変更の後に次の高価な変更が起きるまで十分な数の操作が必要になるよう設計します。四分の一まで減ったら半減する方式は、そのような余裕を作る一例です。ただし最小容量や丸めの規則も定め、許すすべての操作列で再評価します。追加だけで示した計算を、削除を含むAPIの保証としてそのまま表示してはいけません。
一回の遅延上限は別に評価する
償却O(1)でも、ある一回の追加が大量の要素を移す可能性は残ります。音声処理や要求応答など、一回の停止時間が重要な用途では、総費用が小さいことだけでは十分ではありません。事前確保、固定容量、有界キュー、コピーを複数回へ分散する方式などを、失敗時の動作も含めて比較します。実測では平均に加え、容量拡張が起きた時点と遅延分布を見ると、費用が集中する場所を確認できます。償却解析は測定の代わりではなく、測定で見える高価なイベントがなぜ繰り返しにくいかを説明する道具です。モデルの上界と実装の待ち時間を両方示すことで、利用者が保証の範囲を判断しやすくなります。