一个操作序列中，可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小的。
换句话说，对于一个操作序列来讲，平摊分析得出的是这个序列下每个操作的平摊开销。
基本公式为 amortized cost = actual cost + accounting cost，我们记为$$\hat{c}_i = c_i + a_i$$这里，$\forall n, \sum_{i=0}^{n}a_i \geq 0$
Multi-Stack
这里的操作有 push，pop 和 multipop($k$) —— 弹出栈顶的 $k$ 个元素，显然，直观上来说，push 和简单 pop 的操作都是高效的，即其性能都在 $O(1)$ 的样子，也就是说，他们的 Actual Cost 都是 1。
而 multipop 则不同，它每次可能会要求弹出至多 $n$ 个元素，如果进行长度为 n 的操作序列都进行这样的操作，那么最坏情况下的复杂度可以达到 $O(n^2)$。这是一个不太紧的上界。
我们发现，由于栈中每次 pop 元素都是建立在 push 的操作次数的基础上，所有的 pop 操作受到 push 操作的限制。每个元素进栈的同时，都隐含着一次出栈的“未来”，所以，push 操作最多能够 push 共 $O(n)$ 个元素，那么 pop 的次数也至多为 $O(n)$。而每个 push、pop 的代价均为 $O(1)$ ，所以整个栈上的数据操作的复杂度上界可以是 $O(n)$！
说得生动而形象一点，我们用上面的公式来记账。
| Operations | Amortized Cost | Actual Cost | Accounting Cost |
|---|---|---|---|
| push | 2 | 1 | 1 |
| pop | 0 | 1 | -1 |
| multipop | 0 | $min(k,s)$ | -$min(k,s)$ |
其中 $s$ 为当时栈中的元素。
用钱来说，因为 Amortized 本身有“分期偿还”的意思呀~
假设你每次在进行 push 操作的时候，都花 2 块钱，那么你在 push 的时候，只花了1 块，还有 1 块钱就作为存款了。每当你进行 pop 操作，或者是 multipop 操作，我们不再需要花钱啦！！每次出栈一个元素就从存款中扣掉 1 块钱，而每时每刻栈中剩余元素个数都大于等于 0 的啦，所以存款的总和不会为负，$\forall n, \sum_{i=0}^{n}a_i \geq 0$ 自然成立。
Doubling Array
就是一开始分配一定量的内存 A，如果在向这个内存空间插入对象时发现空间不足的话，就重新分配一块比原来大的内存 B，我们就认为 $size(B)=2size(A)$，把原内存 A 中所有的对象都复制到内存 B 中，这时候的代价为 $O(n)$ 然后把新加入的对象增插入到 B 的空余位置中，最后把内存 A 释放掉。呵呵，记得内存泄漏！！
乍一想，可能每次插入都可能要再 malloc 一块空间，代价就是 $O(n)$ 啊，那么$n$ 次操作复杂度就是 $O(n^2)$ 啊！So terrible！！
好了，平摊分析会告诉你上界是 $O(n)$
我们假设一开始这个表是空的，然后向这个表中依次插入 $n$ 个元素，想一想，就会发现，这个操作序列中是不可能连续 $n$ 次出现最坏性能的（怎么可能每次插入都要 double 空间呢？），甚至说，出现最坏性能的机会是比较小的，仅在第 2 的幂的数。除此以外，直接插入就是了，不需要额外申请空间，代价仅仅为 $O(1)$。
所以，我们有Actual Cost$$c_i = \left\{
\begin{array}{ll}
1 & i \neq 2^x,x \in N \\
i+1 & i=2^x,x \in N
\end{array}
\right.$$直接对$c_i$求和，我们可以得到$$\sum_{i=0}^{n} c_i=n+\sum_{i=0}^{\log n} 2^i \leq n + 2n = 3n$$可见，如果平摊的话，每个操作的平均 cost 为 3！所以这样的一个操作，上界是 $O(n)$！
那么为什么不是 2？我们助教也是很认真负责哒。如果每个数插入的时候，插入花了 1，那么在一次 double 的时候，另一块钱就被用完了，以后插入要 double 的时候，就没有存款啦！所以，当代价为 3 的时候，还有两块钱的存款，一块钱用于 double 时自己的花费，另一块钱就是给它前面的所有的已经没有存款的元素用啦~~真是善良！！！
Binary Counting
这是一个二进制计数器，用一个 $k$-bit 的数进行计数，就像当年数字逻辑电路的面包板上的那个玩意儿…基本的置位 set 操作和复位 reset 操作本身的代价都为 $O(1)$。
直观上，最坏情况每个 bit 位都要发生改变，代价就是 $O(k)$，$n$ 次计数操作就是 $O(kn)$。
可是，平摊分析告诉你，上界是 $O(n)$，你应该已经习以为常了吧~~
假设一个 8-bit 的数从高位到低位分别存入数组 $A[7..0]$ 中用于计数，那么每次计数加 1，最低位 $A[0]$ 都需要置位或者是复位。容易知道，$A[1]$ 每 +2 置位或复位，$A[2]$ 每 +4 置位或复位，$\cdots$，更一般地，$A[i]$ 每 +$2^{i}$ 都要置位或者是复位，那么该 bit 就发生变化，所以第 $i$ 位发生 set 或 reset 的次数总共为 $n/2^i$。
对这个通项 $n/2^i$ 求和，值为 $n$ 那么最多也就是( $\log n+1$ )个 bit 就可以表示$$\sum_{i=0}^{\log n}\frac{n}{2^i} < n \sum_{i=0}^{\infty}\frac{1}{2^i}=2n$$下面我们来记账：
| Operations | Amortized Cost | Actual Cost | Accounting Cost |
|---|---|---|---|
| set | 2 | 1 | 1 |
| reset | 0 | 1 | -1 |
Two Stacks, One Queue
用两个栈来实现队列！我们知道栈是先进后出，而队列是先进先出。我们可以用两个栈来实现队列。方法如下：
如果是 Enque 操作，就把元素 push 到栈 S1 中，如果是 Deque 操作，则分为两种情况
$$\left\{
\begin{array}{ll}
popall~S1, pushall~S2, pop~S2 & S2=\emptyset \\
pop~S2 & S2\neq \emptyset
\end{array}
\right.$$
我们假定基本的 pop 和 push 操作、以及判断是否栈为空的代价均为 $O(1)$。
所以，比较简单的 Deque 的 Actual Cost 为 $1+1=2$，而比较复杂的 Deque 操作，则实际代价为 $1+2t$，$t$ 为栈 S1 中的元素个数。
下面，我们进行平摊分析，这里的内在联系是，我们在 push 的时候，先存款 2，用于将这个元素从 S1 中 pop，再 push 到 S2 中去的代价，这样我们的两个 Deque 操作的代价就都是 2 了，只要 S1 中有元素，我们的存款就是非负的，记账如下
| Operations | Amortized Cost | Actual Cost | Accounting Cost |
|---|---|---|---|
| Enqueue | 3 | 1 | 2 |
| Dequeue(Normal) | 2 | 2 | 0 |
| Dequeue(Complex) | 2 | 2+2$t$ | 2$t$ |
Two Queues, One Stack
这是不是真正的 5，用两个队列来实现栈。情况略比上一种情况复杂些。实现方法：每次在进行 pop 操作的时候，要把队列中除最后一个元素外都转移到另一个队列中，然后再进行 Deque 来模拟 pop。总是能保证一个队列为空，另一个队列非空。我们规定判断是否空队列的代价为 $O(1)$，基本的 Deque 和 Enque 操作也都为 $O(1)$。
push 操作：
如果两个队列都空，则 Q1.Enque()；
如果 Q1 非空但 Q2 空，则 Q1.Enque()；
如果 Q1 空但 Q2 非空，则 Q2.Enque()；
pop 操作：
如果两个队列都空，则返回 false；
如果 Q1 非空但 Q2 空，则循环执行 Q2.Enque(Q1.Deque()) 一直到 Q1 中只剩下一个元素，此时返回 Q1.Deque() 的值，即为最后进入 Q1 的元素；执行之后 Q1 变为空，Q2 非空（如果之前 Q1 中不止一个元素的话）。
如果 Q1 空但 Q2 非空，则循环执行 Q1.Enque(Q2.Deque()) 一直到 Q2 中只剩下一个元素，此时返回 Q2.Deque() 的值，即为最后进入 Q2 的元素；执行之后 Q2 变为空，Q1 非空（如果之前 Q2 中不止一个元素的话）。
算法分析：我们每次pop的时候最坏情况下都需要移动队列，每次的代价都是 $n\times O(1)=O(n)$，所以我们的复杂度为 $O(n)$；下面我们看看平摊分析的结果，假设非空队列中有 $t$ 个元素：
push 的 Actual Cost 为 $2=1+1=$ 判空 + Enque；
pop 的 Actual Cost 为 $2t=1+2(t-1)+1=$ 判空 + 转移 + Deque；
每次的 push 的 Accounting Cost 都是 $2n-2$，这样的话，我倒是觉得其实没有这么多啊，如果遇到 pop 操作的话，只需要存下 $2t-2$ 这样的存款，这样 pop 操作的 Amortized Cost 就是 0 了，但是这样似乎失去了平摊分析的意义了啊。。。所以我觉得还是存下 $2n-2$ 的存款吧，每个元素在 pop 的时候最多转移 $n-1$ 次，所以最终 push 的 Amortized Cost 就是 $n$，最后的复杂度为 $O(n^2)$，显然不高效啊！！
5说的就是这个意思，是我大概随便写写的。也不知道这样分析对不对。。。