ならし解析（償却分析）とは？平均計算量の考え方と具体例を解説

アルゴリズムの性能を評価するとき、個々の操作の最悪計算量だけを見ていると、実際の効率を正しく把握できないことがあります。本記事では、そうした場面で役立つならし解析（償却分析：Amortized Analysis）の基本概念と、代表的な解析手法である集計法について、ハッシュテーブルや動的配列の例を交えてわかりやすく解説します。

ならし解析（Amortized Analysis）とは

ならし解析とは、まれに非常に遅い操作が発生するものの、頻繁に実行される大部分の操作は高速であるような場合に、一連の操作全体にかかるコストを平均化して評価する手法です。

データ構造の分野では、ハッシュテーブルや素集合データ構造（Union-Find／Disjoint Set）など、単発の最悪ケースでは過大な評価になってしまう処理の性能分析に広く用いられています。

ハッシュテーブルにおける例

ハッシュテーブルでは、要素の探索や挿入はほとんどの場合 O(1) の定数時間で完了します。しかし、衝突（コリジョン）が発生したときだけは、衝突を解決するために最大で O(n) の処理が必要になります。

このように「通常は速いが、ごくまれに遅くなる」操作を含むデータ構造では、最悪ケースのみに注目すると実際の性能を過小評価してしまいます。そこでならし解析を用いることで、長期的に見た1操作あたりの平均コストを適切に評価できるのです。

集計法（Aggregate Method）

集計法は、ならし解析の中でも最も基本的な手法で、n回の一連の操作全体にかかる総コスト T(n) を求め、それを操作回数 n で割ることで、1操作あたりのならしコストを算出します。

ならしコスト ＝ T(n) ／ n

つまり、大量のデータを扱う場合でも、「全体でどれくらいの総コストがかかるか」を先に見積もれば、1回あたりの実質的なコストを導き出せるという考え方です。

ならし解析の具体例：動的配列への挿入

動的配列（可変長配列）への要素挿入は、通常 O(1) の時間で行えます。ただし、これは挿入先の領域が配列内に空いている場合に限られます。

配列がすでに満杯である場合は、定数時間では挿入できません。このとき、配列はまず現在のサイズを2倍に拡張し、既存の全要素を新しい領域へコピーした上で、要素を挿入します。この一連の処理には O(n) の時間がかかります。

i回目の挿入コスト c(i) の分析

ここで、c(i) を「i回目の挿入にかかるコスト」と定義します。

• 配列に空きがある場合：c(i) ＝ 1（要素を1つ追加するだけ）
• 配列が満杯で拡張が必要な場合：c(i) ＝ i（既存の i−1 個の要素のコピー＋新規挿入）

このコスト列に対して集計法を適用すると、n回の挿入全体の総コスト T(n) は、通常の挿入コスト n と、サイズ倍増時に発生するコピーのコスト（高々 log₂n 回）の和で表され、次のように評価できます。

T(n) ＝ n ＋ ⌊log₂n⌋ ＝ O(n)

したがって、1操作あたりのならしコストは

T(n) ／ n ＝ O(1)

となり、たとえ拡張のたびに O(n) のコピーが発生しても、動的配列への挿入は長期的に見れば定数時間で行えることが証明されます。

まとめ

ならし解析は、まれに発生する高コストな操作を多数の低コストな操作で「均す（償却する）」ことで、データ構造の実際的な性能を評価する強力な手法です。ハッシュテーブルや動的配列のように、最悪ケースと平均ケースのギャップが大きい構造を設計・選定する際には、ぜひ押さえておきたい概念といえるでしょう。