ポテンシャル法

計算の複雑さの理論によれば、ポテンシャル法は、データ構造の償却された時間と空間の複雑さを分析するために実装された方法として定義されます。これは、まれですが高価な操作のコストを排除する一連の操作に対するパフォーマンスの尺度です。

ポテンシャル法では、データ構造の状態を非負の数に変換する関数Φが選択されます。 Sがデータ構造の状態として扱われる場合、Φ（S）は、償却分析で考慮されたがまだ実行されていない作業を示します。したがって、Φ（S）は、その状態で蓄積された位置エネルギーの量を計算するものとして想像することができます。データ構造を初期化する前に、潜在的な値はゼロとして定義されます。あるいは、Φ（S）は、状態Sの無秩序の量、または理想的な状態からの距離を表すものとして想像することができます。

例

データ構造の状態に関する潜在的な関数Φ（「Phi」と読みます）が次の特性を満たすことを示すことができます-

• Φ（a0）=0、ここでa0はデータ構造の開始状態です。
• 計算の過程で発生するデータ構造のすべての状態でΦ（at）≥0。

直感的には、潜在的な関数は、計算の任意の時点でプリチャージされた時間を追跡することができます。それは、高価な操作に支払うために利用可能な節約された時間の量を測定します。それは銀行家の方法での銀行残高のようなものです。しかし、興味深いことに、データ構造の現在の状態にのみ依存します。データ構造をその状態にした計算の履歴は関係ありません。

次に、操作の償却時間を次のように定義します

c +Φ（a'）-Φ（a）、

ここで、cは操作の元のコストであり、aとa'はそれぞれ操作の前後のデータ構造の状態です。したがって、償却時間は、実際の時間にポテンシャルの変化を加えたものとして定義されます。理想的には、各操作の償却時間が短くなるようにΦを定義する必要があります。したがって、電位の変化は、低コストの運用では正、高コストの運用では負として測定する必要があります。