Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 平摊分析
发信站: 哈工大紫丁香 (2002年03月22日14:48:23 星期五), 站内信件

平摊分析
在平摊分析中，执行一系列数据结构操作所需要的时间是通过对执行的所有操作求平均
而得出的。平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通
过对所有操作求平均后，平均代价还是很小的。平摊分析与平均情况分析的不同之处在
于它不牵涉到概率。这种分析保证了在最坏情况下每个操作具有平均性能。
本文将讨论平摊分析技术中最常用的三种技术：
聚集方法 —— 可以用这种方法确定一个n个操作的序列的总代价的上界T(n)。每个操作
的平摊代价可表示为T(n)/n；
会计方法 —— 用它可确定每个操作的平摊代价。当有一种以上的操作时，每种操作都
可有一个不同的平摊代价。这种方法对操作序列中的某些操作先“多记帐”，将多记的
部分作为对数据结构中的特定对象上预付的存款存起来。在该序列中稍后要用到这些存
款以补偿那些对它们记的“帐”少于其实际代价的操作。
势能方法 —— 它与会计方法的相似之处在于要确定每个操作的代价，且先对某些操作
多记帐以补偿以后的不足记帐。这种方法将存数作为数据结构的“势能”来维护，而不
是将存款与数据结构中的单个对象联系起来。
我们将用两个例子来说明这三个模型。第一个例子是个栈，它有一个新的操作MULTIPOP
，它可一次弹出几个对象。另一个例子是个二进计数器，它利用操作INCREMENT从0开始
计数。
在阅读本文时，读者应记住在平摊分析中所记的“帐”只是为了分析之用，它们不应出
现在代码中。例如，当在采用会计方法时，如果将一存款赋予一个对象，在代码中就没
有必要对其属性credit[x]赋一个相应的值了。
通过做平摊分析而获得的对某种数据结构特性的认识有助于优化设计。例如，后文中我
们将用势能方法来分析一个动态扩充和收缩的表。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]