ポテンシャル法

計算複雑性理論において、ポテンシャル法はデータ構造の償却時間と空間の複雑さを分析するために使用される方法であり、これは、頻度は低いがコストのかかる操作のコストを平滑化する一連の操作のパフォーマンスの尺度です。^{[1] [2]}

ポテンシャル法では、データ構造の状態を非負の数値にマッピングする関数 Φ が選択されます。Sがデータ構造の状態である場合、 Φ( S ) は、償却分析で計算された (「支払われた」) がまだ実行されていない作業を表します。したがって、 Φ( S ) は、その状態に蓄えられたポテンシャルエネルギーの量を計算するものと考えることができます。^{[1] [2]} データ構造を初期化する操作の前のポテンシャル値はゼロと定義されます。あるいは、 Φ( S ) は、状態Sの無秩序の量、または理想的な状態からの距離を表すものと考えることができます。

oを、あるデータ構造に対する一連の操作の中の任意の個別の操作とします。S before_は操作o前のデータ構造の状態を表し、S _afterは操作oが完了した後の状態を表します。Φが選択されると、操作oの償却時間は次のように定義されます。

${\displaystyle T_{\mathrm {償却} }(o)=T_{\mathrm {実際} }(o)+C\cdot (\Phi (S_{\mathrm {後} })-\Phi (S_{\mathrm {前} })),}$

ここで、 Cは負でない比例定数（時間単位）であり、解析中は一定でなければなりません。つまり、償却時間は、操作にかかった実際の時間と、操作によって生じた電位差のC倍と定義されます。 ^{[1] [2]}

ビッグ O 表記法を使用して漸近的な計算複雑さを研究する場合、定数因子は無関係であるため、定数Cは通常省略されます。

不自然な外観にもかかわらず、一連の操作の合計償却時間は、同じ一連の操作の実際の時間の 有効な上限を提供します。

任意の操作シーケンスに対して、次を定義します。 ${\displaystyle O=o_{1},o_{2},\dots ,o_{n}}$

• 償却期間の合計:${\displaystyle T_{\mathrm {償却} }(O)=\sum _{i=1}^{n}T_{\mathrm {償却} }(o_{i}),}$
• 実際の合計時間:${\displaystyle T_{\mathrm {実際} }(O)=\sum _{i=1}^{n}T_{\mathrm {実際} }(o_{i}).}$

それから：

${\displaystyle T_{\mathrm {償却} }(O)=\sum _{i=1}^{n}\left(T_{\mathrm {実際} }(o_{i})+C\cdot (\Phi (S_{i})-\Phi (S_{i-1}))\right)=T_{\mathrm {実際} }(O)+C\cdot (\Phi (S_{n})-\Phi (S_{0})),}$

ここで、ポテンシャル関数値のシーケンスは、初期および最終のポテンシャル関数値以外のすべての項がペアで打ち消される 伸縮シリーズを形成します。これを並べ替えると、次のようになります。

${\displaystyle T_{\mathrm {実際} }(O)=T_{\mathrm {償却} }(O)-C\cdot (\Phi (S_{n})-\Phi (S_{0})).}$

および なので、個々の操作の償却時間が実際の時間と大きく異なる場合でも、償却時間を使用して一連の操作の実際の時間の正確な上限を提供できます。 ${\displaystyle \ファイ (S_{0})=0}$${\displaystyle \Phi (S_{n})\geq 0}$${\displaystyle T_{\mathrm {実際} }(O)\leq T_{\mathrm {償却} }(O)}$

通常、償却分析は、入力シーケンスに関する最悪のケースの仮定と組み合わせて使用​​されます。この仮定では、 X がデータ構造によって実行される可能性のある操作のタイプであり、nが特定のデータ構造のサイズを定義する整数 (たとえば、含まれる項目の数) である場合、タイプXの操作の償却時間は、サイズnのデータ構造に対するすべての可能な操作シーケンスと、シーケンス内のタイプXのすべての操作o _iの中で、操作o _iの償却時間の最大値として定義されます。

この定義では、一連の操作を実行する時間は、一連の操作の各タイプの償却時間にそのタイプの操作の数を掛けることによって見積もることができます。

動的配列は、項目の配列を維持するためのデータ構造であり、配列内の位置へのランダム アクセスと、配列のサイズを 1 つずつ増やす機能の両方を可能にします。Java では「ArrayList」型として、Python では「list」型として 使用できます。

動的配列は、長さNの項目の配列Aと、これまでに使用された配列内の位置を表す数値n  ≤  Nで構成されるデータ構造によって実装できます。この構造では、動的配列へのランダムアクセスは、内部配列Aの同じセルにアクセスすることによって実装できます。また、 n  <  Nの場合、動的配列のサイズを増やす操作は 、 n を増分するだけで実装できます。ただし、n  =  Nの場合、 A のサイズを変更する必要があり、一般的な方法は、 A を長さ 2 nの新しい配列に置き換えてサイズを 2 倍にすることです。^[3]

この構造はポテンシャル関数を使用して分析できます。

Φ = 2 n  −  N

サイズ変更戦略により、A は常に少なくとも半分満たされるため、この潜在的な関数は、期待どおり常に非負になります。

サイズ増加操作がサイズ変更操作につながらない場合、Φ は定数の 2 だけ増加します。したがって、操作の実際の時間が一定であることと、電位が一定に増加することが組み合わさって、このタイプの操作の償却時間は一定になります。

ただし、サイズ増加操作によってサイズ変更が行われると、サイズ変更後に Φ の潜在的な値はゼロに減少します。新しい内部配列Aを割り当て、古い内部配列から新しい配列にすべての値をコピーするには、実際の時間は O( n ) かかりますが、(比例定数C を適切に選択すると) 潜在的な関数の減少によって完全にキャンセルされ、操作の合計償却時間は再び一定になります。

データ構造の他の操作（配列サイズを変更せずに配列セルの読み取りと書き込み）では、ポテンシャル関数は変化せず、実際の時間と同じ一定の償却時間を持ちます。^[2]

したがって、このサイズ変更戦略とポテンシャル関数を選択すると、ポテンシャル法はすべての動的配列操作が一定の償却時間を要することを示しています。これを、操作シーケンスの償却時間と実際の時間に関する不等式と組み合わせると、個々の操作の一部は線形の時間がかかる可能性があるにもかかわらず、 n 回の動的配列操作のシーケンスは最悪の場合でも O( n ) の実際の時間がかかることがわかります。^[2]

動的配列に配列サイズを増やす操作だけでなく減らす操作も含まれる場合、ポテンシャル関数が負にならないように変更する必要があります。これを行う 1 つの方法は、上記の Φ の式をその絶対値に置き換えることです。

次の操作をサポートする スタックを考えてみましょう。

• 初期化 - 空のスタックを作成します。
• プッシュ - スタックの一番上に 1 つの要素を追加し、スタックを 1 増やします。
• Pop( k ) -スタックの上からk個の要素を削除します。kは現在のスタックサイズ以下です。

Pop( k )はO( k )時間を必要としますが、すべての操作にはO(1)の償却時間がかかることを示したいと思っています。

この構造はポテンシャル関数を使用して分析できます。

Φ = スタック内の要素数

この数値は、必要に応じて常に負でない数値になります。

Push 操作には一定の時間がかかり、Φ が 1 増加するため、償却時間は一定になります。

Pop操作にはO( k )の時間がかかりますが、Φもkだけ減少するため、償却時間も一定になります。

これは、 m 個の操作のシーケンスは最悪の場合でも O( m ) の実時間を要することを証明しています。

2 進数として表され、次の操作をサポートする カウンターを考えてみましょう。

• 初期化: 値 0 のカウンターを作成します。
• Inc: カウンターに 1 を追加します。
• 読み取り: 現在のカウンター値を返します。

この例では、トランス二分法マシンモデルは使用していませんが、代わりに増分におけるビット操作ごとに1単位の時間を必要とします。 Inc には償却時間が O(1) かかることを示したいと思っています。

この構造はポテンシャル関数を使用して分析できます。

Φ = 1 に等しいビット数 =ハミング重み(カウンタ)

この数値は常に負ではなく、必要に応じて 0 から始まります。

Inc 操作は最下位ビットを反転します。次に、LSB が 1 から 0 に反転すると、次のビットも反転します。これは、最終的にビットが 0 から 1 に反転するまで続き、その時点で反転は停止します。カウンターが最初にk 1 ビットで終了した場合、合計k +1 ビットを反転します。実際の時間はk +1かかり、潜在時間はk −1 減少するため、償却時間は 2 です。したがって、 m 回のInc 操作を実行する実際の時間はO( m ) です。

ポテンシャル関数法は、フィボナッチヒープ（項目の削除に対数償却時間がかかり、他のすべての操作には一定の償却時間がかかる優先キューの一種）の解析によく使用されます。 ^[4]また、操作ごとに対数償却時間を持つ自己調整型のバイナリ検索ツリーであるスプレイツリーの解析にも使用できます。^[5]