償却計算量解析で便利な手段であるポテンシャルの扱いについての簡単な部分を書きます。本稿では時間計算量についてのみを扱い、「計算量」は時間計算量を指します。

可変長配列

以下のクエリを処理する可変長配列を考えます。

• $empty()$
  • 空の列を作成する
• $lookup(i)$
  • $i$ 番目の要素を取得する
• $push(x)$
  • 末尾に $x$ を追加する

このデータ構造はメモリ領域を保持し、そのうち先頭からいくらかが実際に要素で埋まっているという構造を持ちます。保持している領域の大きさを $capacity$、入っている要素の数を $size$ で表します。各クエリは以下のアルゴリズムで実現されます。

• $empty()$
  • 何もしない
• $lookup(i)$
  • 保持している領域の $i$ 番目の位置にアクセスする
• $push(x)$
  • $capacity=size$ ならば $2\ast capacity$ の領域を確保し、全ての要素を移す
  • 末尾の位置に $x$ を書き込む

全てのクエリが償却 $O(1)$ で実現されることを、計算量の貯金を用いて示します。

$push$ で領域の拡大が起こるとき、定数倍を除くと高々 $size$ の計算量が必要になります。
ここで、$push$ の度に $2$ だけ計算量を「貯金」することを考えてみます。この貯金は後で重い処理をするときに使用して計算量を均す目的で使用されます。逆に、貯金をしたクエリは貯金の分計算量が増えたとみなします。この例では $2$ は定数であるため、貯金する分はクエリ辺り $O(1)$ であり最終的なオーダーには影響しません。
領域の拡大が起こるとき、前に拡大が起きてから $2\ast \frac{size}{2}=size$ だけ貯金が貯まっています。よってこの貯金を使うことで償却 $O(1)$ と評価することが出来ます。

ポテンシャル

ポテンシャル $\Phi$ を導入することで、前述した手続きが扱いやすくなります。これはデータ構造の状態に対して数値を与える関数で、その状態のデータ構造に貯まっている貯金の量に対応しています。実際に必要となる計算量を実計算量と呼ぶことにすると、ポテンシャルによる償却計算量の表示は以下のようになります。

償却計算量
$=$ 実計算量 $+\Delta \Phi$
$=$ 実計算量 $+\Phi ($クエリ後$)-\Phi ($クエリ前$)$

貯金をするとき $\Phi$ は増加し、償却計算量は実計算量より大きくなります。
貯金を崩す時 $\Phi$ は減少し、その分償却計算量は小さくなります。

「現在貯まっている貯金量」「どのクエリでどれほど貯金を増やすか、減らすか」などの複雑な条件を、１つの関数にまとめ上げることが出来ました。このような手法を物理学者法と呼びます。

可変長配列の場合、以下のように定義すると上手く行きます。

$\Phi :=2\ast size-capacity$

これを元にもう一度 $push$ の計算量解析をしてみます。$size,capacity$ はそれぞれクエリが呼ばれた瞬間の値とします。

• 領域拡大を伴わない場合
  • 実計算量 $=1$
  • $\Phi ($クエリ後$)=2\ast (size+1)-capacity$
  • $\Phi ($クエリ前$)=2\ast size-capacity$
  • 償却計算量 $=1+2=3\in O(1)$
• 領域拡大を伴う場合 ($size=capacity$)
  • 実計算量 $=size$
  • $\Phi ($クエリ後$)=2\ast (size+1)-2\ast size$
  • $\Phi ($クエリ前$)=2\ast size-size$
  • 償却計算量 $=size+2-size=2\in O(1)$

$empty,lookup$ は $\Phi$ を変化させないため実計算量が償却計算量と等しくなり、$O(1)$ です。

$pop$ に対応する

可変長配列に新たなクエリを追加します。

• $pop()$
  • 末尾の要素を削除する

$pop$ を繰り返し呼ぶと、保持している領域に対して要素数が少ししかない状況が発生します。$push$ 時の拡大と同様に、適切に縮小を行うことで空間計算量を $O(size)$ に削減します。アルゴリズムは以下の通りです

• $pop()$
  • $4\ast size<capacity$ の場合、新たに $2\ast size$ の領域を確保し、要素を全て移す
  • 末尾の要素を無視する

$pop$ も含めた解析は元のポテンシャルだと上手く行かないので、少しだけ拡張します。

$\Phi :=|2\ast size-capacity|$

$pop$ の償却計算量を評価します。

• 領域の縮小を伴わない場合
  • 実計算量 $=1$
  • $\Phi ($クエリ前$)=|2\ast size-capacity|$
  • $\Phi ($クエリ後$)=|2\ast (size-1)-capacity|$
  • 償却計算量 $\le 1+2=3\in O(1)$
• 領域の縮小を伴う場合 ($4\ast size<capacity$)
  • 実計算量 $=size$
  • $\Phi ($クエリ前$)=|2\ast size-capacity|=capacity-2\ast size<2\ast size$
  • $\Phi ($クエリ後$)=|2\ast (size-1)-2\ast size|=2$
  • 償却計算量 $<size+2-2\ast size=2-size\in O(1)$

$empty,lookup,push$ についての解析は全く同様ですので省略します。

ポテンシャルに必要な性質

償却計算量の定義に沿って考えることで、ポテンシャルに対する制限を導出します。
$N$ 回のクエリを行うとし、$i$ 回目のクエリの実計算量を $T_i$、${\Phi }_i$ を $i$ 回目のクエリの直前の値とします。最初は ${\Phi }_0$ で全クエリの終了後には ${\Phi }_N$ になっています。

実計算量の和 $=\sum T_i$
償却計算量の和 $=\sum (T_i+{\Phi }_{i+1}-{\Phi }_i)={\Phi }_N-{\Phi }_0+\sum T_i$

償却計算量の和は実計算量の和を下回ってはいけないので、${\Phi }_N-{\Phi }_0\ge 0$ が必要十分条件です。また、$\Phi$ は平行移動しても問題ないので ${\Phi }_0=0$ とすることにします。以上をまとめると次の条件を得ます。

• ${\Phi }_0=0$
• ${\Phi }_N\ge 0$
• (上手く解析に使える)

${\Phi }_N\ge 0$ はすなわち、貯金はよくても借金はしてはいけないことを意味しています。借金のある状態で操作を終了すると踏み倒しになってしまうと解釈できます。

Two Stack Queue

https://scrapbox.io/data-structures/Sliding_Window_Aggregation
アルゴリズム自体の説明はこちらを参照してください。
ポテンシャルを以下のように設定すると上手く行きます。

$\Phi :=size(back\_stack)$

各要素の移動する回数に着目する解析も鮮やかですが、ポテンシャルもかなり分かりやすいのではないでしょうか。

解析の注意点

一つのデータ構造の解析で異なるポテンシャルを使わない

データ構造は大抵複数の種類のクエリを処理できますが、それぞれで異なるポテンシャルを用いることはできません。あるクエリを処理するとき、他のクエリで使っているポテンシャルが増加しているかもしれないためです。
そのような「計上されない不正な貯金」が発生しない場合、全ての和をポテンシャルとして定義することで上手く行くこともあります。

実計算量が抑えられていても償却計算量を確認する

たとえ実計算量が $O(1)$ のクエリがあったとしても、他のクエリの償却解析のためにポテンシャルを導入したら、そのクエリもポテンシャルの増減を考える必要があります。それによって、償却計算量が実計算量よりオーダーのレベルで大きくなる場合もあります。

解析の途中で $O$ 記法を使う時は気を付ける

ポテンシャルを $O$ で不適切に扱うと、誤った解析をしてしまう可能性があります。$\Phi$ を $x$ 増加させて償却計算量に計上した後、$\Phi =O(x)$ であるとして $2x$ の貯金を消費すると、貯金量より多く消費しているため不正です。

まとめ

• 貯金を考えると償却計算量の解析ができる
• ポテンシャルは貯金の便利な定式化

参考文献

Chris Okasaki. Purely Functional Data Structures
アスキードワンゴ　純粋関数型データ構造