ポテンシャル法とは？データ構造の償却計算量を解析する手法を解説

ポテンシャル法とは

計算複雑性理論において、ポテンシャル法（potential method）とは、データ構造の償却時間計算量および空間計算量を解析するために用いられる手法です。償却計算量とは、一連の操作全体にわたるパフォーマンスを測定するための指標であり、頻度は低いものの高コストとなる操作のコストを平準化して評価できる点が大きな特徴です。

ポテンシャル関数の基本的な考え方

ポテンシャル法では、データ構造の状態を非負の数値へと変換する関数 Φ（ファイ）を選択します。S をデータ構造のある状態とすると、Φ(S) は「償却解析上ですでに見込みとして計上されているが、まだ実行されていない仕事の量」を表します。これは、その状態に蓄えられたポテンシャルエネルギー（位置エネルギー）の量を計算しているとイメージすると分かりやすいでしょう。

データ構造を初期化する前の時点では、ポテンシャル値は 0 と定義されます。また、Φ(S) を「状態 S における乱れの大きさ」や「理想的な状態からの距離」と捉えることも可能です。

ポテンシャル関数が満たすべき性質

例として、データ構造の状態に対して定義されるポテンシャル関数 Φ は、以下の性質を満たす必要があります。

• Φ(a₀) = 0：a₀ はデータ構造の開始時の状態（初期状態）を表します。
• Φ(aₜ) ≥ 0：計算の過程で現れるすべての状態 aₜ に対して、ポテンシャル値は非負でなければなりません。

直感的に言えば、ポテンシャル関数は計算の任意の時点における「前払い済みの時間」を追跡する役割を果たします。つまり、高コストな操作の支払いに充てられる、貯め込まれた時間の残高を測定しているのです。これは銀行家法（banker's method）における銀行残高のようなものですが、興味深いことに、ポテンシャル値は計算の履歴には依存せず、データ構造の現在の状態のみによって決まります。

償却時間の定義

ある操作の償却時間は、次の式で定義されます。

c + Φ(a′) − Φ(a)

ここで、c は操作本来の実際のコスト、a と a′ はそれぞれ操作前後におけるデータ構造の状態を表します。すなわち、償却時間とは「実際の時間 ＋ ポテンシャルの変化」として定義されます。

理想的には、各操作の償却時間が小さくなるように Φ を設計します。そのためには、低コストの操作ではポテンシャルの変化が正（貯蓄）として現れ、逆に高コストの操作では負（取り崩し）として測定されるようにするのが望ましいといえます。