平摊分析（Amortized Analysis）-- Potential Method

      势能方法将已预付的工作表示成一种“势能”，在需要的时候可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。 开始时，先对一个初始数据结构D_0执行n个操作。对每个i=1，2，...，n，设为第i个操作的实际代价，D_i为对数据结构D_{i-1}作用第i个操作的结果。势函数将每个数据结构D_i映射为一个实数(D_i)。第i个操作的平摊代价根据势函数的定义为

每个操作的平摊代价为其实际代价加上由于该操作所增加的势。n个操作的总的平摊代价为：

 

如果我们能定义一个势函数使得(D_n) >= (D_0)，则总的平摊代价\sum_{i=1}^n (\hat{c}_i)就是总的实际代价的一个上界。若能证明对所有的i，(D_i) >= 0，则可以保证预先支付。

这里的平摊代价依赖于所选择的势函数。不同的势函数可以会产生不同的平摊代价，但它们都是实际代价的上界。

 

[Example]栈操作(PUSH，POP，MULTIPOP)

 

定义栈上的势函数为栈中对象的个数。空栈为D_0, 则(D_0)=0。因为栈中的对象数始终非负，故栈D_i具有非负的势。

 

        如果在一个包含s个对象的栈上的第i个操作是PUSH，则势差为(s+1) - s = 1， 故PUSH操作的平摊代价为=1+1 =2。

        如果栈上的第i个操作是MULTIPOP(S,k)，且弹出了k'=min(k, s)个对象。该操作的实际代价为k'，势差为-k'，因些MULTIPOP操作的平摊代价为k'-k'=0。

        如果第i个操作是POP，则其势差为s-(s+1)=-1，其平摊代价为1-1 = 0。

 

我们已经证明了每一个栈操作的平摊代价都是O(1)，这样n个操作序列的总平摊代价就是O(n)。它是总的实际代价的一个上界，所以n个操作的最坏情况代价为O(n)。

 

假设有势函数，使得对所有的i都有(D_i) >= (D_0)，但是(D_0) != 0。证明存在一个势函数使得(D_0)=0，(D_i) >= 0，对所有i>=0， 且用表示的平摊代价与用表示的平摊代价相同。(习题17.3-1)

    证明：记(D_0)=k，令(D_i)=(D_i) - k，则(D_0)=0，(D_i) >= (D_0) - k = 0。且有 (D_n) - (D_0) = (D_n) - (D_0)， 故它们表示的平摊代价是一样的。