摊还分析 算法导论 算法

摊还分析

摊还分析的定义

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

1. 聚合分析

1.1. 聚合分析的定义

  聚合分析是摊还分析中的一种，先来介绍如何利用聚合分析进行摊还代价的计算。在聚合分析中，我们需要计算总代价（一般为最坏情况下的n个操作的时间复杂度），然后除以n得到每个操作的平均代价，或者称为摊还代价。这种分析的方法就叫做聚合分析。

  设想一个有限集合OP = {PUSH,POP,POP,...,PUSH,PUSH},其中PUSH(S, x):将对象x压入栈S中。POP(S):将栈S的栈顶对象弹出，并返回该对象。对空栈调用POP会产生一个错误。由于两个操作都是O(1)时间的，我们假定其代价为1。因此一个n个连续操作的PUSH和POP的总代价为n，而n个连续操作的实际运行时间为O(n)。

1.2. 练一道题

  假定我们对一个数据结构执行一个由n个操作组成的操作序列，当i严格为2的幂时，第i个操作的代价为i，否则代价为1。数学表述如下:

$C_i = \begin{cases} i, & \text{如果 $i$ 为2的幂次} \\ 1, & \text{否则} \end{cases}$
我们一开始，可以先用列表的方法分析代价，如下表：

  因为每逢2的幂次其代价才会与序号相等，所以将它们加起来，正好是呈等比数列排序，那么可推出如下公式成立：$\sum_{i=1}^nC_i \le n + \sum_{j=0}^{lgn}2^j \lt n - (1-2^{lgn}) = 3n$
  不等式推导的结果可知n次操作的总时间复杂度为O(3n)，即O(n)。可得其摊还代价为O(n)/n=O(1)常数级的时间复杂度。即在n次操作中的平均时间复杂度为常数级别，这是令人惊奇的，毕竟直觉上可能得不到这样的结果。聚合分析需要计算n次操作的总代价，而往往计算这样的总代价并不轻松。

2. 核分析

2.1. 核分析的定义

  用核算法(accounting method)进行摊还分析时，我们对不同操作赋予不同费用，赋予某些操作的费用可能多于或少于实际的代价。我们将赋予一个操作的费用称为它的摊还代价。即建立一个存储操作代价的银行，我们为操作赋予的超出器实际价值的差额称为信用。当后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额。

2.2. 练一道题

  我们使用核算法重新计算1.2.的题目，首先我们做一点微小的改动，改动之后的公式如下:
$C_i = \begin{cases} 3, & \text{如果 $i$ 为2的幂次} \\ 1, & \text{否则} \end{cases}$
  仅仅将原来公式里的i替换成了3（从1.2.题目的总代价O(3n)中，我们尽管可以猜到）。要看替换是否成立，主要取决与我们分配给每个操作的信用之和是否足够支付其差额。即分配的代价之和必须是原来总代价的上界。列表分析：

  其实可以从1.2.中的聚合分析得知保留信用不会为负数（即我们建立的代价银行不会破产），那么我们就可以说我们分配的摊还代价足以支付每个操作的代价，那么就有：$\sum_{i=1}^nC_i \le \sum_{i=1}^n \widetilde C_i = 3n$

  另外，虽然在聚合分析中我们已经得知了上界是小于3n的，但我们也可以通过计算得到每个分配的代价d确切的数值，由n个操作总代价是可以计算得到的：$\sum_{i=1}^nC_i = n + \sum_{j=1}^{lgn}2^j-lgn$。要有足够的信用用于分配，则要使以下式子成立：$dn - \left[ n + \sum_{j=1}^{lgn}2^j-lgn \right] \ge 0$。$dn - \left[ n + \left( 2n-1 \right) - lgn \right] \gt \left( d-3 \right)n \ge 0$综上得，$d \ge 3$。即证明了选择摊还代价为3时满足题设。

3. 势能法

3.1. 势能法的定义

  在势能法摊还分析中并不将预付的代价表示为数据结构中特定对象的信用，而是表示为“势能”，将势能释放即可用来支付未来操作的代价。我们将势能与整个数据结构而不是对象相关联。

3.2. 练一道题

  还是以1.2.题为例。首先，不妨假定i次操作为PUSH栈操作，即有定义$C_i \begin{cases}i, & \text{当i为2的幂时（等价位MUTIPUSH（i））} \\ 1, & \text{否则（等价于PUSH）}\end{cases}$
  又定义$\phi(D_0)=0$，初始时的栈为空，那么第n次操作得到栈的势能为$\phi(D_n)=n+\sum_{j=1}^{lgn}2^j-lgn$。那么有$\phi(D_n) - \phi(D_{n-1}) = 1 + \sum_{i=1}^{lgn}2^i - \sum_{j=1}^{lg(n-1)}2^j)+lg(1-\frac{1}{n})=3$。所以得到摊还代价为：$\widetilde C_i\begin{cases} i+3, & \text{i为2的幂次} \\ 4, & \text{否则}\end{cases}$
又有$\sum_{i=1}^{n}C_i=\sum_{i=1}^n \widetilde C_i - \phi(D_n) + \phi(D_0)$，注意其中$\sum_{i=1}^n \widetilde C_i = \phi(D_n) + \sum_{i=1}^n3$，所以总代价即为$\sum_{i=1}^nC_i=3n$，摊还代价即为O(1)，这样我们就完成了使用势能法分析了这道题目。