償却計算量
償却計算量とは
一連の操作全体に対して計算量を評価し、そのコストを各操作に配分して求める一回あたりの計算量。
例
可変長配列を例に説明する｡
前提 :
- はじめに要素数 0、容量 1 の可変長配列が作成される。
- 要素は 1 個ずつ末尾に追加され、追加は N 回行われる。
- 容量が不足した場合、容量は 2 倍に拡張される。
- 拡張時には、新しい配列が確保され、既存の全要素が新しい配列へコピーされる。
- 1 要素の書き込みおよびコピーの時間計算量は O(1) とする。
- 新しい配列の確保にかかる時間計算量は O(1) とする。
各処理の時間計算量:
- 初期配列をつくる : O(1)
- N個の要素を書き込む : O(N)
- 拡張用の配列を確保する (容量不足の回数分) : O(log N)
- 拡張時に既存要素をコピーする (容量不足の回数分) : O(N)
すべての操作の時間計算量は､ O(1) + O(N) + O(N) + O(log N) = O(N)
容量不足が発生した全ての回における拡張処理の時間計算量は､ O(N) + O(log N) = O(N)
すべての操作の時間計算量は O(N) 。これを追加操作の回数 N で割ればいいので、償却時間計算量は O(N) / N = O(1) ｡
::note::
可変長配列の操作の例
現在の配列 (容量
):[a, b, c, d]
"e" を追加したい｡
容量が足りないので拡張する｡
4 × 2 = 8 の容量で配列を作成する｡
[_, _, _, _, _, _, _, _]
拡張元の配列の値を､拡張先にコピーする｡
コピー1回目 : [a, _, _, _, _, _, _, _]
コピー2回目 : [a, b, _, _, _, _, _, _]
コピー3回目 : [a, b, c, _, _, _, _, _]
コピー4回目 : [a, b, c, d, _, _, _, _]
"e" を追加する｡
[a, b, c, d, e, _, _, _]
::