Potential Method —— amortized analysis

之前搬运有关 amortized analysis 内容时，分析方法介绍了 aggregate method 和 accounting method。有时 accounting method 也作 banker method (回想起 OS 里面也有对应的银行家算法)。这次补充介绍 potential method 作为 amortized analysis 的一种方法。

有关 amortized analysis 的介绍，以及一些基础模型可见算法设计搬运（2）——Amortized Analysis。

公式

如果已经有了 amortized cost 相应的了解那么就可以直接进入到 potential method 的公式了。

$T_{amortized}(o) = T_{actual}(o)+C·\Delta \Phi$
亦作
$T_{amortized}(o) = T_{actual}(o)+C·(\Phi(S_{after})-\Phi(S_{before}))$

等式左边反映的是对于某个数据结构操作 $o$ 的 amortized 复杂度。 $o$ 指的在该数据结构上一系列操作中的任意一次单独操作。 $T_{actual}(o)$ 指该次操作实际的复杂度。 $S$ 表示的是该数据结构的状态， $\Phi$ 是一个映射函数，将状态 $S$ 映射成一个非负整数。 $C$ 是任意非负固定常数。

我看这个wiki上面的对于potential method的翻译译作“电位法”。这个状态 $\Phi S$ 可以理解为当前数据结构的混乱状态或者距理想状态的差距。越不混乱那么就越接近理想，越有序。

因为amortized analysis的引入就是考虑到有些操作有时会复杂度很高，而有些时候复杂度又很低，我们想知道一系列操作下来，这个操作的“均摊”复杂度(相比最坏情况更贴合实际)怎么样。之前的两种方法都是要结合一个 sequence 的操作来解该操作的“均摊”复杂度——Aggregate的思路是先求sequnce整体复杂度再平均，Accounting则是使操作能为数据结构存储一定的令牌，复杂度低的积攒令牌，而面对复杂度高的确保令牌消耗不透支，来求得“均摊”复杂度。而现在电位法只需要考虑某一次操作，它的实际复杂度以及它对势能的改变的贡献就能得知该操作的“均摊”复杂度了。其思路大致与accounting类似，只不过视角不一。一般低复杂度的操作天然会使状态更混乱，而复杂度高的操作一般都会涉及到维护问题，需要“人为”的降低混乱程度。(参考热力学第二定律?)

举例分析

在算法设计搬运（3）——Heaps中我们用aggregate，eager binomial heaps 的insert和deleteMin的“均摊”复杂度分别是 $\Theta(1)$ 和 $\Theta(\log n)$ 。

eager binomial heap 的 insert

我们用 $\Phi$ 表示当前保存了当前二项堆的数量(假设一开始存储了 $n$ 个节点)。插入首先要把一个node link到collection里面，O(1)。初始 $\Phi = \log n$ 。
假设这次操作进行了合并了 $k$ 次，actual cost = $2 + k$ 。

insert

而每一次合并则会使 binomial heap 的数量 -1。由此插入后的 $\Phi = 1+ \log n - k$ 。所以 $T_{amortized}(o) = 2 + k + C·(1 + \log n - k - \log n) = 2 + C - (C - 1) \cdot k \leq 2 +C = \Theta(1)$
Insert worst-case 的均摊复杂度 $\Theta(1)$ 。(actual cost = $2 + k$ ，1是link， $1+k$ 是 $k$ 次合并要扫描 $k+1$ 个位置的 heap，从order低到高扫)

eager binomial heap 的 deleteMin

初始 $\Phi = \log n$ ，首先找minimum $O(\log n)$ 。
假设minimum是 $B_k$ 的 root，那么 remove root之后产生 $k$ 个新heap， $B_0,B_1,...,B_{k-1}$ ，link进collection 的 $cost = k$ 。

那么假设进行了 $m$ 次合并，且已知扫描了 $k$ 个位置， $cost = m+k+O(\log n)$ 。最终 $\Phi = \log n - 1 + k - m$
$T_{amortized}(o) = m+2k + C\cdot (\log n -1+k-m -\log n) = O(k+\log n)$
因为 $k,m = O(\log n)$ ，所以最终的均摊复杂度其实 $=O(\log n)$ 。(需不需要存min 指针并更新都一样)

extract-Min

(这里的Union指合并两个binomial heap，先扫描如果有同order则比较二者根大小，小者作为 rank+1的新根，同时order+1，大者根的 sibling指向小者此时的 child link，然后新根的 child link 再指向大者。结果就是大的作为小者的最左子树——细节，图片来源于 Stony Brook CSE548 lecture-9)