ポテンシャル解析

ならし計算量を解析するテクニックとしてポテンシャル解析というものがある。
ポテンシャル解析とは何かを簡単に説明し、いくつかの簡単な解析例を示す。

二進カウンタ問題

例として、二進カウンタ問題をポテンシャル解析を用いて解析する。

二進カウンタは以下のような機能を持つデータ構造である。

  • n ビットの二進列を持つ
  • 二進列に 1 を足す

1 を足す操作を n 回行うことを考える。i 回目の操作のコストを c_i とすると

\begin{align}
\sum_{i=1}^n c_i
\end{align}

が全体のコストになる。これを何とかして見積もりたい。しかし c_i は二進カウンタの状態に応じて値が変化してしまう。
状態の変化も考慮して計算量を見積もるのは一般に難しい。

ここでポテンシャル関数 \Phi(D) を使う。ポテンシャル関数\Phi(D)D\to \mathbb{R}_{\ge 0} の関数であれば何でもいい。Dは二進カウンタでありうるすべての状態の集合である。

今回は \Phi(D) を二進列に含まれる 1 の個数と定義すると解析がうまくいく。たとえば

\begin{align}
\Phi(0000)=0\\
\Phi(0010)=1\\
\Phi(1010)=2
\end{align}

である。一般に実行コストは末尾にある連続する 1 の個数とみなせる。たとえば、

\begin{align}
cost(0000)=0\\
cost(0001)=1\\
cost(0010)=0\\
cost(0111)=3
\end{align}

である。さてここでならしコスト(amortized cost)というものを(実コスト)+(ポテンシャルの変化量)として定義する。たとえば

\begin{align}
amo(0000)=cost(0000)+\Phi(0001)-\Phi(0000)=1 \\
amo(0001)=cost(0001)+\Phi(0010)-\Phi(0001)=1 \\
amo(0010)=cost(0010)+\Phi(0011)-\Phi(0010)=1 \\
amo(0011)=cost(0011)+\Phi(0100)-\Phi(0011)=1 \\
amo(0100)=cost(0100)+\Phi(0101)-\Phi(0100)=1
\end{align}

である。実をいうと、どのような二進列であっても、今回のポテンシャル関数を用いた amortized cost は 1 となる。ゆえに i 回目の操作の amortized cost を a_i とすると

\begin{align}
\sum_{i=1}^{n} a_i
&=
\sum_{i=1}^{n} (c_i+\Phi_{i+1}-\Phi_{i}) \\
&=\sum_{i=1}^{n}c_i+\Phi_{n+1}-\Phi_1 \\
n&=\sum_{i=1}^{n}c_i+\Phi_{n+1}
\end{align}

となる。このことから

\begin{align}
\sum_{i=1}^{n}c_i \le n
\end{align}

が示された。これがポテンシャル解析というものである。c_iの総和を求める代わりにa_iの総和を求めることで、結果的にc_iの総和の上界が得られたのである。

ポテンシャル関数に求められる性質

  • 初期状態は 0 である
  • 関数値は非負でなければならない
  • (必須ではないが)コストが軽い操作は、実コストが小さい代わりにポテンシャルを増加させる。
  • (必須ではないが)コストが重い操作は、実コストが大きい代わりにポテンシャルを減少させる。

skew heap の解析

ヒープのHL分解を用いる。右の子と結ぶ heavy edge (right heavy edge) の本数をポテンシャルとして設定する。実コストは merge を呼び出した回数としておこう。

辿るときに使った heavy edge の本数を H、light edge の本数を L とすると、実コストは H+L+1 である。HL分解の性質から L \le \lg n が言える。

node *merge(node *x, node *y) {
	if (x == nullptr) return y;
	if (y == nullptr) return x;
	if (x->val > y->val) swap(x, y);

	// x->r のサイズはここで大きくなる。
	// x->r がもともと heavy edge だった場合は、merge 後も heavy edge である。
	// x->r がもともと light edge だった場合は、merge 後に heavy edge に変わるかもしれない。
	x->r = merge(x->r, y);

	// H本のheavy edge はこの操作で左側に移動する。
	// L本のlight edge はこの操作により、たかだか L 本が right heavy edge となる。
	swap(x->l, x->r);

	return x;
}

f:id:pekempey:20170207172114p:plain

辿るときに使った heavy edge はすべて左側に移動し、新たに増える heavy edge はたかだか  \lg n 本しかないため、\Delta\Phi \le \lg n - H である。よって amortized cost は、

\begin{align} H+L+1+\Delta\Phi \le H+ \lg n + 1 + \lg n - H \end{align}

link-cut tree (HL decomposition)

link-cut tree の HL 分解による解析をおこなう。skew heap と解析は似ている。

いずれかのパスに属している辺を solid, 属していない辺を dashed と呼ぶことにする。

木のHL分解を考えたとき、dashed heavy の本数をポテンシャルとして設定する。解析するのは expose のみとする。その他の解析は自明である。

expose(v)の実コストを v から根へのパス上にある dashed heavy の本数とする。

dashed heavy の本数を  H、dashed light の本数を L とする。このとき実コストは H+L である。L\le \lg n が成り立つので、H+L\le H+\lg n である。

expose を呼ぶことで、根から v へのパス上にある dashed heavy はすべて solid heavy に変わる。根から v へのパス上にある dashed light は solid light に変わるが、このとき新たに dashed heavy を生み出すかもしれない。しかしその個数は \lg n で抑えられる。

f:id:pekempey:20170207171420p:plain

よって amortized cost は

\begin{align} H+L+\Delta\Phi \le H+\lg n + \lg n - H= 2\lg n \end{align}

この記事は以下の記事のために書きました。

pekempey.hatenablog.com