摊还分析的背景
- 对于某个数据结构而言，其上的大部分操作代价较小，而很少的操作代价很大，如果要分析该数据结构的操作序列的代价下界，所取的下界难以展示出该数据结构的真正特点。
- 某些数据结构中的操作的代价并不是容易计算的。
摊还分析
- 依据某些方法，求某个数据结构的一个操作序列中操作的平均代价，更好地展示该数据结构的特性。
- 摊还分析不涉及概率，其只是依照数据结构的特点，分析其最坏情况，得到尽可能低的上界以及尽可能符合该数据结构特点的平均代价。
- 平均代价为：T(n) / n。而摊还代价，个人认为应当与平均代价进行区别，其只是在摊还分析中的某个中间量。
摊还分析的具体方法
聚集方法
- 将某个数据结构的操作进行整体查看，这也是聚集的含义，直接分析最坏情况下的总代价T(n)，直接计算平均代价T(n) / n。
- 该方法不实用，对于某些数据结构，很难明确每个操作的代价。
会计方法(核方法)
- 直接定义当前数据结构的操作的代价，我们称之为摊还代价，这仅仅是一个中间量。一个操作的摊还代价可能多于或少于该操作的实际代价。
- 定义存款。如果当执行某一操作时，该操作的摊还代价超出其实际代价，那么二者之间的差额将被存入数据结构中的特定对象，这部分差额可以当后续的操作的摊还代价小于实际代价时，进行弥补。定义这些差额为存款。
- 当定义摊还代价时，需要保证，对于任意的操作序列，其总存款不可以小于0。由于我们希望凭借总摊还代价求解出一个尽可能低的上界，所以必须保证对于任意的操作序列，总摊还代价不小于总真实代价。而存款 = 总摊还代价 - 总真实代价，所以对于任意的操作序列，存款不小于0.
- 当确定满足条件的摊还代价，可以直接求n个操作的最长情况下的总摊还代价，这就是T(n)的一个上界，那么平均代价也可以唾手可得。
- 会计方法必须要求开始时，原数据结构为null，因为无法确定初始结构的存款。只有初始结构为null时，其存款记为0。
势方法
- 定义势能。势能与会计方法中的存款非常相似，都具有支付未来操作的代价的特点，但是与存款存入数据结构的特定对象不同，势能与整个数据结构相关联。由此可以定义势函数Φ，Φ是由数据结构D映射到一个实数Φ(D)。Φ(D)量化了势能的大小。
- 定义数据结构操作的摊还代价。令Ai表示第i个操作的实际代价，Di为在数据结构Di-1上执行第i个操作得到的数据结构。那么可以定义第i个操作的摊还代价为：Bi = Ai+ Φ(Di) - Φ(Di-1)。即每个操作的摊还代价等于其实际代价加上此操作引起的势能变化。
- 保证，对于任意的操作序列，Φ(Di) ≥ Φ(D0)，一般而言，定义势函数Φ(D0) = 0，Φ(Di) ≥ 0。原因如下，由于我们希望凭借摊还代价求解出一个尽可能低的上界，而由摊还代价的定义可以求得，对于长度为n的操作序列，总摊还代价 = 总真实代价 + Φ(Dn) - Φ(D0)。那么只需要保证Φ(Dn) - Φ(D0) > 0，那么总摊还代价就是总真实代价的上界。而我们所要探究的是所有的操作序列，n可以为任意值，所以，只得保证对于任意的操作序列，Φ(Di) ≥ Φ(D0)。
- 当确定合适的势函数后，可以计算每个操作的摊还代价，进而分析在最坏情况下，n个操作序列的总摊还代价，这就是T(n)的一个上界，那么平均代价也可以唾手可得。
- 要定义势函数，可以考虑当真实代价较大的操作作用于数据结构时，数据结构势的变化应当是突然降低，之后执行其他操作，数据结构势再慢慢累计。
例子
栈操作问题
对于一个栈，定义其三种操作，计算其平均代价。
- pop()，弹出并返回栈顶元素。代价：O(1)。
- push()，将某元素压入栈中。代价：O(1)。
- multipop(s,k)，如果栈s中元素个数大于k，栈s中弹出k个元素，否则，栈s弹出所有元素。代价：O(min(s,k))。
聚集方法：
- 当将这三个操作聚集，可以观察到其组成的操作序列具有以下特点：栈上pop操作的次数(可以将multipop(s,k)转换为pop())至多等于push操作的次数。那么，在最坏情况下，T(n) = O(n)，平均代价为O(1)。
会计方法
- 定义pop()以及multipop()的摊还代价为0，push()摊还代价为2，存款存入栈中的每个元素，可能很简单的证明得到该摊还代价满足对于任意的操作序列，其总存款不可以小于0。进而，在最坏情况下，即n个操作序列中的所有操作为push()，那么T(n) ≤ 2n ，T(n) = O(n)，那么平均代价为O(1)。
势方法
- 定义势函数为Φ，由当前数据结构映射到栈中的元素个数，显然，这是可以保证：对于任意的操作序列，Φ(Di) ≥ Φ(D0)。那么可以依次计算得到pop()的摊还代价为 1 - 1 = 0，multipop()的摊还代价为 k - k = 0，push的摊还代价为 1 + 1 = 2。那么，在最坏情况下，n个操作均为push操作，那么，其总摊还代价为 2n。则T(n) ≤ 2n ，T(n) = O(n)，那么平均代价为O(1)。
k位二进制计算器问题
该计算器中有一个0/1数组A[1...k-1]，该数组表示一个k位的二进制数x，其中x的最低位保存在A[0]中，而x的最高位保存在A[k-1]中。初始时，x = 0。定义操作INCREMENT如下：
INCREMENT(A)
i = 0；
while i<length[A] and A[i]=1 Do
A[i] = 0;
i = i+1;
If i<length[A] Then A[i] = 1；
求解INCREMENT操作的代价，代价标准为INCREMENT操作中对0以及1反转的次数。
聚集方法：
- 将n个INCREMENT操作进行聚集，那么可以观察到，A[0] 反转n次，A[1]反转⌊ n / 2 ⌋ 次，A[2]反转⌊ n / 22⌋ 次，以此类推，可以得出A[i] 反转了⌊ n / 2i ⌋次。那么T(n) = Σ(i = 0 : k-1) ⌊ n / 2i ⌋ < nΣ(i = 0 : ∞) ⌊ / 2i ⌋ = 2n。那么T(n) = O(n)，而T(n) / n = O(1)。
会计方法
- 我们可以定义，当0被反转为1时的摊还代价为2，而1被反转为0时的摊还代价为0。那么当进行一次0反转为1的操作时，其真实代价只是1，另外具有存款1，此存款存于数组的1中，该存款可以用于其后操作的复位的真实代价抵消。也就是说INCREMENT算法中第3~5行的复位操作将不会付出任何代价，只是第6行会付出2的代价。所以INCREMENT操作的摊还代价为2。那么最坏情况下，n个操作均为INCREMENT，总摊还代价为2n，则T(n) = O(n)，而T(n) / n = O(1)。
势方法
- 定义势函数为Φ，由当前数据结构映射到当前数组中1的个数。显然，这是可以保证，对于任意的操作序列，Φ(Di) ≥ Φ(D0)。之后计算INCREMENT操作的摊还代价，假设第i个INCREMENT操作，将Ti个1进行复位，同时还需要将0置为1，所以其真实代价至多为 Ti + 1，之所以为至多，是因为当操作后数组全部为0是，不需要加1。if Φ(Di) = 0，then Φ(Di-1) = Ti = k。if Φ(Di) != 0，then Φ(Di) = Φ(Di-1) + 1 - Ti。但是不管那种情况Φ(Di) ≤ Φ(Di-1) + 1 - Ti。那么Φ(Di) - Φ(Di-1) ≤ 1 - Ti。那么INCREMENT操作摊还代价C ≤ Ti + 1 + Φ(Di) - Φ(Di-1) ≤ Ti + 1 + 1 - Ti = 2。那么，最坏情况下，n个操作均为INCREMENT，总摊还代价小于2n，则T(n) = O(n)，而T(n) / n = O(1)。
- 较为复杂的是，需要处理当前数据结构数组中全为1的情况。上述分析采用了同时处理两种情况的方式，也可以分别处理，这样反而清晰明了。
另外，依据势方法可以进一步讨论该问题，可以从计数器不是从0的这一状态开始进行分析。
- 假设计数器初始时包含b0个1，经过n个INCREMENT操作后包含bn个1，其中0 ≤ b0,bn ≤ k。那么，总真实代价 = 总摊还代价 - Φ(Dn) + Φ(D1)。而我们已知INCREMENT操作的摊还代价 ≤ 2，那么总真实代价 ≤ Σ(i=1: n)2 - bn + b0 = 2n- bn + b0。由于0 ≤ b0,bn ≤ k，只要 k = O(n)，那么总真实代价就是O(n)。换句话说，如果至少执行n = Ω(k)个INCREMENT操作，不管计数器初值是什么，其实际代价都是O(n)。