聚合分析：我们证明对所有n，一个n个操作的序列最坏情况下花费的总时间为T(n), 因此在最坏情况下每个操作的平均代价或摊还代价为T(n)/n。
所以，聚合分析中的每个操作的聚合代价都是相同的。那怎么分析呢？聚合分析要求我们要总体看问题。
下面举几个例子。
1. 栈操作
- push(s)每次只能压一个数据，所以规定操作的代价为1。
- pop(s)每次只能弹一个数据，所以也规定操作的代价为1。
- mutlipop(s,k)，内部实现的是一个循环弹出k个元素，每执行一次的代价为k（k<n,n为栈的最大容量）。
- 栈大小为n。
现在分析下由n个push、pop、mutlipop组成的n行操作序列的最坏情况下的时间复杂度是多少？(即a次push，b次pop, c次mutlipop，a+b+c=n)
初步分析：首先mutlipop最坏情况代价为O(n)，因为栈的大小最大为n, 从而n个操作的最坏情况代价为O(n^2)，因为序列可能包含O(n)个mutlipop操作，
每个执行的代价为O(n)。虽然这个分析是正确的，但这个O(n2)并不是一个确界。
聚合分析：通过聚合分析考虑整个序列的n个操作，可以得到更好的上界。将一个对象压入栈中，我们至多将其弹出一次，所以可以执行的
pop次数最多与push的次数相当，即最多n次。而总的操作为n次，每个操作要么pop，要么push，所以时间复杂度为O(2n-2)，即
push, push, ..., push, mutlipop(n-1)，因此摊还代价为O(n)/n=O(1)。
注意：这里分析的是最坏的代价，即每次操作都有一次栈的操作，即push或pop。mutlipop的调用可能并不操作栈，即弹出0个元素，
若其啥都不做，则复杂度为O(1)。
2. 二进制计数器递增
问题描述：一个k位二进制计数器的初值为0，我们用一个位数组A[0..k-1]作为计数器，其中A.length=k，最低位保存在A[0]中，最高位保存在A[k-1]中，
二进制的数值为∑A[i]×2i。二进制数加一操作代码如下：
INCREMENT(A)
i = 0
while i < A.length and A[i] == 1 // 前几位清0
A[i] = 0
i++
if i < A.length:
A[i] = 1
分析n个INCREMENT操作组成的序列的代价。
初步分析：最坏情况下INCREMENT执行一次花费O(k)时间，因为n个操作序列需要O(nk)时间。
聚合分析：因为不可能每次INCREMENT都翻转所有的二进制位，每次调用INCREMENT时，A[0]确实都会翻转，而A[1]只是每两次调用翻转一次。
如下所示：
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1
...
一次A[1]只会翻转n/2次。类似的A[2]每四次调用才会翻转。所以A[i]会翻转n/2i次，因此n个INCREMENT操作翻转的总次数为
Σn/2i = nΣ1/2i ，i=0,1,2,...,k，由幂级数可知当k趋于无穷大时Σ1/2i=2，所以Σn/2i < 2n，i=0,1,2,...,k，故摊还代价为O(n)/n = O(1)。