摊还分析

引言

在一个数据结构上可以进行多种操作，这些操作中代价最高的是O(n)。由这些操作组成的n个操作的序列，总代价在最差的情况下是多少？是O(n)吗，可以是O(n)吗？ 衡量在某个数据结构上进行的一系列操作最坏情况下的平均代价，这就是摊还分析要做的事情。

方法

  1. 聚合分析：分析n个操作序列的总代价，从而得到平均代价。
  2. 核算法：分析每一个操作的摊还代价。例如在栈操作中，push操作的摊还代价设置为2，一份代价自己用，另一份留作今后的pop操作；pop操作的摊还代价设置为0。
  3. 势能法：与核算法类似，使用较早的操作来补偿之后的操作。设置势能函数。

    例子

    动态表的扩张和收缩，比如std::vector<T>。通过摊还分析（核算法，势能分析）可以简单得出结论：
  • 装填因子上升到1时，进行表扩张，此后装填因子变成1/2；
  • 装填因子下降到1/4时，才进行表收缩，此后装填因子上升到1/2。
  • 这样，可以保证单个insert和delete操作的摊还代价（最坏情况）为常数。