《算法导论》第17章-摊还分析 17.1 聚合分析 && 17.2 核算法&&17.3 势能法

17.1 聚合分析

一、引入

在摊还分析(amortized analysis)中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。这样，我们就可以说明一个操作的平均代价是很低的，即使序列中某个单一操作的代价很高。摊还分析不同于平均情况分析，它并不涉及概率，它可以保证最坏情况下每个操作的平均性能。

二、栈操作

利用聚合分析，我们证明对所有n，一个n个操作的序列最坏情况下花费的总时间为T(n)。因此，在最坏情况下，每个操作的平均代价，或摊还代价为T(n)/n。注意，此摊还代价是适用
于每个操作的，即使序列中有多种类型的操作也是如此。

1、分析栈操作

push(S,x):将对象x压入栈。
pop(S):将栈S顶部元素弹出，并返回该对象，对空栈调用pop会报错。
multipop(S,k):将S栈顶k个元素弹出

multipop(S,k)
while not STACK-EMPTY(S) and k>0
	pop(S)
	k = k-1
1
2
3
4

（1）分开分析：序列中一个MULTIPOP操作的最坏情况代价为O(n)，因为栈的大小最大为n。因此，任意一个栈操作的最坏情况时间为O(n)，从而一个n个操作的序列的最坏情况代价为
O(n²)，因为序列可能包含O(n)个MULTIPOP操作，每个的执行代价为O(n)。虽然这个分析是
正确的，但我们通过单独分析每个操作的最坏情况代价得到的操作序列的最坏情况时间O(n²),
并不是一个确界。
（2）聚合分析：我们考虑整个序列的n个操作，可以得到更好的上界。当将一个对象压入栈后，我们至多将其弹出一次。因此，对一个非空的栈，可以执行的POP操作的次数(包括了MULTIPOP中调用POP的次数)最多与PUSH操作的次数相当，即最多n次。因此，对任意的n值，任意一个由n个PUSH、POP和MULTIPOP组成的操作序列，最多花费O(n)时间。一个操作的平均时间为O(n)/n=O(1)。 在聚合分析中，我们将每个操作的摊还代价设定为平均代价。因此，在此例中，所有三种栈操作的摊还代价都是0(1)。

三、二进制计数器递增

INCREMENT(A)
i = 0
while i < A.length and A[i]==1
	A[i] = 0
	i = i+1
if i < A.length
	A[i] = 1
1
2
3
4
5
6
7

17.2 核算法

一、引入

1、用核算法(accounting method)进行摊还分析时，我们对不同操作赋予不同费用，赋予某些操
作的费用可能多于或少于其实际代价。我们将赋予一个操作的费用称为它的摊还代价。当一个操作的摊还代价超出其实际代价时，我们将差额存入数据结构中的特定对象，存入的差额称为信用。对于后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。因此，我们可以将一个操作的摊还代价分解为其实际代价和信用(存入的或用掉的)。
不同的操作可能有不同的摊还代价，因此_这种方法不同于聚合分析中所有操作都赋予相同摊还代价的方式_。
2、

二、栈操作

用餐盘作为例子：
通过按摊还代价缴费，我们可以支付任意的栈操作序列(的实际代价)。假定使用1美元来表示一个单位的代价。我们从一个空栈开始。当将一个盘子放在一叠盘子的最上面，我们用1美元支付压栈操作的实际代价，将剩余的1美元存为信用(共缴费2美元)。在任何时间点，栈中的每个盘子都存储了与之对应的1美元的信用。每个盘子存储的1美元，实际上是作为将来它被弹出栈时代价的预付费。当执行一个POP操作时，并不缴纳任何费用，而是使用存储在栈中的信用来支付其实际代价。为了弹出一个盘子，我们将这个盘子的1美元用于支付即可，这对于pop和multipop都一样。
因此，对任意n个PUSH、POP、MULTIPOP操作组成的序列，总摊还代价为总实际代价的上界。由于总摊还代价为O(n)，因此总实际代价也是。

三、二进制计数器递增

在摊还分析中，对一次置位操作，我们设其摊还代价为2美元。当进行置位时，用1美元支付置位操作的实际代价，并将另外1美元存为信用，用来支付将来复位操作的代价。在任何时刻，计数器中任何为1的位都存有1美元的信用，这样对于复位操作，我们就无需缴纳任何费用，使用存储的1美元信用即可支付复位操作的代价。
while 循环中复位操作的代价用该位储存的1美元来支付。INCREMENT 过程至多置位一次，因此，其摊还代价最多为2美元。计数器中1的个数永远不会为负，因此，任何时刻信用值都是非负的。所以，对于n个INCREMENT操作，总摊还代价为O(n)，为总实际代价的上界。

17.3 势能法（限于时间，只能划重点了）