データ構造の償却時間計算量とは？償却解析の基礎と計算方法を解説

償却解析（Amortized Analysis）とは

償却解析は、ごく一部の操作が非常に遅い一方で、頻繁に実行される大半の操作は高速であるような状況で用いられる分析手法です。データ構造の分野では、ハッシュテーブルや素集合データ構造（Disjoint Set／Union-Find）などの性能評価において重要な役割を果たします。

例えばハッシュテーブルでは、探索の時間計算量はほとんどの場合 O(1) ですが、ときに O(n) の操作が発生することがあります。要素の検索や挿入は通常、定数時間で完了する処理です。しかし衝突（コリジョン）が発生した場合には、その解決のために O(n) の操作が必要になることがあります。

集計法（Aggregate Method）

集計法は、一連の操作全体にかかる総コストから償却コストを求めるための手法です。大量のデータをまとめて追加するようなケースでは、次の式によって償却コストを計算できます。

n 回の操作列に対するコストは、以下のように表されます。

Cost(n回の操作) ÷ n ＝（通常の操作のコスト ＋ 高価な操作のコスト）÷ n

償却解析の具体例：動的配列

動的配列では、指定されたインデックスへの要素挿入は O(1) 時間で実行できます。しかし、そのインデックスが配列の現在の範囲外である場合、定数時間での処理はできません。この場合、まず配列のサイズを2倍に拡張してから、要素を挿入することになります。

動的配列において、c_i を i 回目の挿入にかかるコストとすると、次のように定義できます。

ci ＝ 1 ＋（i−1 が2の冪乗である場合は i−1、それ以外は 0）

つまり、通常の挿入はコスト1ですが、配列の拡張が必要なタイミング（i−1 が2の冪乗のとき）だけ、それまでの要素のコピー分として大きなコストが加算されます。

n 回の挿入全体の平均コスト（償却コスト）は、次の不等式で評価できます。

(Σ ci) ÷ n ≤（n ＋ Σ 2j）÷ n ＝ O(n) ÷ n

ここで j は 1 から ⌊log₂(n−1)⌋ までの範囲を取ります。この結果から、n 回の挿入全体にかかるコストは O(n)、つまり1回あたりの償却コストは O(1) に抑えられることが分かります。これこそが、動的配列への挿入が「平均的に定数時間」とみなせる理由です。