平摊分析（Amortized Analysis）

平摊分析这一章，CLRS的英文版一直没有读懂，不知道是不是心太浮了。今天把中文版的拿出来再读一读，希望愚钝的头脑能开一开窍。

这一部分总标为高级分析技巧，想来也不是那么好理解的，所以一遍不懂就再来一遍，百遍之内定能见其义了！

在amortized analysis中，执行一系列数据结构操作(push, pop, multipop, etc)所用时间是通过对执行的所有操作（n个这样的操作）求平均得出的。平摊分析可以用来证明在一系列操作中，通过对所有操作求平均之后即使其中单一操作具有较大的代价，平均代价还是很小的。

常用的平摊分析有3种：

1. 聚集分析（Aggregate analysis）。用于确定一组n个操作序列的总代价的上界T(n)。这样每个操作的平均代价就是T(n)/n。把平均代价当作每个操作的平摊代价，因此所有的操作有相同的平摊代价。
2. 记帐方法（Accouting method）。其中要确定每个操作的平摊代价。每种操作都可有一个不同的平摊代价。这种方法对操作序列中的某些操作先“多记帐”，将多记的部分作为对数据结构中的特定对象上“预付的存款（prepaid credit）”存起来。在该序列中稍后将用到这些存款，以补偿那些对它们记的“账”少于其实际代价的操作。
3. 势能方法（Potential method）。与记账方法的相似之处在于要确定每个操作的平摊代价，而且可能先对操作多记账以补偿以后的不足记账。这种方法将存款作为数据结构整体的“势能”来维护，而不是将存款与数据结构听单个对象联系起来。

(Note: 平摊分析中所记的“账”只是为了分析所用，它们不必要也不应该出现在代码中。)

 

一、Aggregate analysis

在这种分析中要证明对所有的n，由n个操作所构成的序列的总时间在最坏情况下为T(n)。因些每个操作的平均代价（平摊代价，amortized cost）为T(n)/n。

[Example]

栈操作，在栈已有的两个操作(PUSH(S,x)和POP(S))上增加一个MULTIPOP(S,k)，作用是弹出栈S的k个栈顶对象当当(少于k个则全部弹出)。PUSH和POP的运行时间都是O(1)，故n个PUSH和POP操作的序列的总代价为\Theta(n)。MULTIPOP(S,s)的代价为min(s,k), k为栈中元素个数。

考虑一个n个操作（由PUSH，POP，MULTIPOP组成）的整个序列的较好的上界。事实上，虽然一次MULTIPOP操作的代价可能较高，但当作用于一个初始为空的栈上时上时，任意一个包含n个PUSH，POP和MULTIPOP操作的序列其代价至多为O(n)，因为一个对象每次入栈后至多只能被弹出一次，所以在一个非空栈上调用POP的次数（包含在MULTIPOP中调用的）至多等于PUSH操作的次数，也就是最多n次。因些对任意的n个PUSH，POP，MULTIPOP操作的序列的总时间为O(n)。每个操作的平均代价为O(n)/n = O(1)。在聚集分析中，把每个操作的平摊代价指派为平均代价。所以这三个栈操作的平摊代价都是O(1)。

 

二、Accounting method

在记账方法中我们对不同的操作赋予不同的费用，某些操作的费用比它们的实际代价或多或少。对一个操作的收费的数量称为平摊代价。当一个操作的平摊代价超过它的实际代价时，两者的差被作为存款（credit），并赋予数据结构中的一些特定对象。存款可以在以后用于补偿那些其平摊代价低于其实际代价的操作。这样我们可以将一个操作的平摊代价看作两部分：其实际代价与存款（或被储蓄或被用完）。

如果希望通过对平摊代价的分析来说明每次操作的最坏情况平均代价较小，则操作序列的总的平摊代价就必须是该序列的总的实际代价的一个上界。且这种关系必须对所有的操作序列都成立。

记为第i个操作的实际代价，平摊代价用 表示，则有：

 

 

由这个不等式可以知道数据结构中的总存款不能是负的。

[Example]仍以栈操作（PUSH，POP，MULTIPOP）为例，对它们赋予以下的平摊代价：

PUSH              2，

POP                0，

MULTIPOP      0，

注意三个平摊代价都是O(1)。

我们需要说明的是，通过这种平摊代价收费，可以支付任何的栈操作序列（即使得总的存款非负）。因为每个PUSH操作都将产生花费1（即PUSH的实际操作），同时产生1的存款(2-1=1)。而POP操作将产生1的花费，这只能从PUSH产生的存款中取得，对MULTIPOP的每个POP操作也如此。这样对任意的n，总的存款都非负。因些总的平摊代价是O(n)，总的实际代价也是O(n)。

 

 

啊，这样写好累啊，明天再写Potential method吧...