平摊分析

平摊分析（英语：Amortized analysis）在计算机科学中，是用于算法分析中的方法，平摊分析常用于分析资料结构（动态的资料结构），在使用平摊分析前须知道资料结构各种操作所可能发生的时间，并计算出最坏情况下的操作情况并加以平均，得到操作的平均耗费时间。平摊分析只能确保最坏情况性能的每次操作耗费的平均时间，并不能确认平均情况性能。

一个简单的例子，一个长度为 ${\displaystyle n}$ 的list，在list的最后要加入一笔新的资料此时要花费的操作时间为 ${\displaystyle O(n)}$，此时也是加入新的资料的最糟糕的情况。但是，一个 ${\displaystyle n}$ 个插入的操作序列仍然可以在 ${\displaystyle O(n)}$ 的时间内完成，因为剩下的插入可以在常数时间内完成，因此 ${\displaystyle n}$ 个插入可以在 ${\displaystyle O(n)}$ 的时间内完成。因此每操作的平摊耗费为 ${\displaystyle O(n)/n=O(1)}$。

注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中，我们平均化所有可能的输入；在概率算法的概率分析中，我们平均化所有可能的随机选择；在平摊分析中，我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。^[1]

平摊分析中几种常用的技术:

• 聚合分析决定 ${\displaystyle n}$ 个操作序列的耗费上界 ${\displaystyle T(n)}$，然后计算平均耗费为 ${\displaystyle T(n)/n}$。^[1]
• 记账方法确定每个操作的耗费，结合它的直接执行时间及它在对运行时中未来操作的影响。通常来说，许多短操作增量累加成“债”，而通过减少长操作的次数来“偿还”。^[1]
• 势能方法类似记账方法，但通过预先储蓄“势能”而在需要的时候释放。^[1]

平摊分析种类

聚集法(Aggregate method)

计算n个操作的时间复杂度上限T(n) 平摊T(n)至每一个操作，每一个操作的平摊成本是T(n)/n

记帐法(Accounting method)

执行花费较低的operations时先存credit未雨绸缪, 供未来花费较高的operations使用

对每个操作定义一个合法的平摊成本(amortized cost) 假设${\displaystyle c_{i}}$为第i个操作的actual cost，${\displaystyle {\hat {c_{i}}}}$为第i个操作的amortized cost

若${\displaystyle c_{i}<{\hat {c_{i}}}}$，则credit=${\displaystyle {\hat {c_{i}}}-c_{i}}$，我们把credit存起来(deposited)，未来可以提取(withdraw) 若${\displaystyle c_{i}>{\hat {c_{i}}}}$，则提取credit

设定每个操作的平摊成本(amortized cost)后，要做valid check确保credit不可以是0，也就是说 ${\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}}$

位能法(Potential method)

定义一个位能函数(potential function)${\displaystyle \Phi (D)}$，将资料结构D(例如: 堆叠)的状态对应到一个实数

${\displaystyle D_{0}}$: 资料结构D的初始状态

${\displaystyle D_{i}}$: 资料结构D经过${\displaystyle i}$个操作后的状态

${\displaystyle c_{i}}$: 第${\displaystyle i}$个操作的actual cost

${\displaystyle {\hat {c_{i}}}}$: 第${\displaystyle i}$个操作的amortized cost

定义${\displaystyle {\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})}$

${\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}=\sum _{k=1}^{n}(c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=(\sum _{k=1}^{n}c_{i})+\Phi (D_{n})-\Phi (D_{0})}$

为了满足${\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}}$

我们定义${\displaystyle \Phi (D_{n})-\Phi (D_{0})\geq 0}$ , 通常令${\displaystyle \Phi (D_{0})=0}$ 和 ${\displaystyle \Phi (D_{n})\geq 0}$

例子

堆叠(stack)的平摊分析

我们定义一个堆叠有下列操作

操作(operation)	说明	actual cost
S.push(x)	将一个元素x放入堆叠S中	${\displaystyle O(1)}$
S.pop()	把堆叠S中最上面的元素取出	${\displaystyle O(1)}$
S.multi-pop(k)	一次pop k个元素	${\displaystyle O(\min(\left\vert S\right\vert ,k))}$

S.mult-pop(k)的程式码如下

def multi_pop(k):
	while (not S.empty()) and (k>0):
		S.pop()
		k -= 1

接下来我们分别使用聚集法(aggregate method), 记帐法(Accounting method), 位能法(Potential method)求出"堆叠一个操作的平摊成本是O(1)"

使用聚集法(aggregate method)分析堆叠操作的平摊成本

令${\displaystyle n_{push}}$是S.push(x)的执行次数，${\displaystyle n_{pop}}$是S.pop()的执行次数，${\displaystyle n_{multi-pop}}$是S.multi-pop(k)的执行次数

${\displaystyle n=n_{push}+n_{pop}+n_{multi-pop}}$为总执行次数

操作(operation)	actual cost	执行次数
S.push(x)	${\displaystyle O(1)}$	${\displaystyle n_{push}}$
S.pop()	${\displaystyle O(1)}$	${\displaystyle n_{pop}}$
S.multi-pop(k)	${\displaystyle O(\min(\left\vert S\right\vert ,k))}$	${\displaystyle n_{multi-pop}}$

因为一个堆叠S如果是空的，就不能执行pop了，也就是说可以pop或multi-pop的元素个数不会超过S中push进去的元素个数

所以${\displaystyle n_{pop}+n_{multi-pop}\leq n_{push}}$

假设${\displaystyle T(n)}$是执行${\displaystyle n}$个操作的时间复杂度上限

${\displaystyle T(n)=O(1)\times n_{push}+O(1)\times n_{push}=O(n)}$

所以堆叠一个操作的平摊成本为${\displaystyle O(n)/n=O(1)}$

使用记帐法(Accouting method)分析堆叠操作的平摊成本

我们假设S.push(x), S.pop(), S.multi-pop(k)的amortized cost分别为2, 0, 0，如下表所示

操作(operation)	actual cost ${\displaystyle c_{i}}$	amortized cost ${\displaystyle {\hat {c_{i}}}}$
S.push(x)	1	2
S.pop()	1	0
S.multi-pop(k)	${\displaystyle O(\min(\left\vert S\right\vert ,k))}$	0

Valid Check 证明: ${\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}}$
${\displaystyle {\color {Red}proof:}}$ push进入堆叠S的元素会存入credit $1 pop(S), multi-pop(S, k) 会取出这些元素的credit $1

因此每个操作的平摊成本是O(1)

使用位能法(potential method)分析堆叠操作的平摊成本

我们定义位能函数${\displaystyle \Phi (D)}$为执行i个操作后，堆叠内的元素个数

${\displaystyle \Phi (D_{0})=0}$ ，因为堆叠一开始是空的

${\displaystyle \Phi (D_{i})\geq 0}$ ，因为堆叠的元素个数一定${\displaystyle \geq 0}$

计算堆叠S每一个操作的平摊成本

操作(operation)	平摊成本(amortized cost) ${\displaystyle {\hat {c_{i}}}}$
S.push(x)	${\displaystyle {\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})=1+(\left\vert S\right\vert +1)-\left\vert S\right\vert =2}$
S.pop()	${\displaystyle {\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})=1+(\left\vert S-1\right\vert )-\left\vert S\right\vert =0}$
S.multi-pop(k)	${\displaystyle {\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})=k+(\left\vert S-k\right\vert )-\left\vert S\right\vert =k-k=0}$

总平摊成本 ${\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}=2\times n_{push}=O(n)}$，所以堆叠单一个操作的平摊成本是${\displaystyle O(n)/n=O(1)}$

动态数组

动态数组的平摊分析

考虑一个随元素个数增加而增长的动态数组，比如Java的ArrayList或者C++的std::vector。如果我们的数组大小从4开始，那么来向其中增加四个元素的时间就是一个常数。然而，若要将第五个元素加入其中，那么会花费更多时间，因为我们此时必须要创建一个两倍于当前数组大小的数组（8个元素），把老元素拷贝到新数组中，然后增加一个新元素。接下来的三次加入操作也同样会花费常数时间，然后在数组被填满后则又需要一轮新的加倍扩充。

一般地，如果我们考虑任意一个任意的n大小的数组并对其进行n + 1次加入操作。我们注意到，所有的加入操作都是常数时间的，除了最后一个，它会花费${\displaystyle O(n)}$时间在大小加倍上。因为我们进行了n + 1次加入操作，我们可以将数组加倍的时间平摊到所有的加入操作上，因此得到加入操作的平均时间是${\displaystyle {\tfrac {nO(1)+O(n)}{n+1}}=O(1)}$。它是一个常数。^[1]

队列

使用Ruby实现的伫列，一个先进先出资料结构:

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

伫列操作及特性参考伫列条目，enqeue及deqeue操作时间复杂度为常数， 否则，dequeue需要${\displaystyle O(n)}$时间将所有元素从输入数组添加到输出数组中，其中n是输入数组的当前长度。 从输入复制n元素后，我们可以在输出数组再次为空之前执行n出队操作，每次操作都需要一个恒定的时间。 因此，我们可以仅在${\displaystyle o(n)}$时间执行一系列n出列操作，这意味著每个出列操作的摊销时间是${\displaystyle O(1)}$ 。^[2]

或者，我们可以收取将任何项目从输入数组复制到输出数组的成本，以及该项目的早期排队操作。 该计费方案将入队的摊还时间加倍，但将出列的摊还时间减少到${\displaystyle O(1)}$。

通常用法

• 在常见场合，我们把能很好平摊分析的算法称为“平摊算法”。
• 在线算法通常使用平摊分析。

参考资料

^[3]

1. Kozen, Dexter. CS 3110 Lecture 20: Amortized Analysis. Cornell University. Spring 2011 [14 March 2015]. （原始内容存档于2018-10-03）.
2. Grossman, Dan. CSE332：Data Abstractions (PDF). cs.washington.edu. [2015年3月14日]. （原始内容存档 (PDF)于2015年4月2日）.
3. MIT 6.046J Design and Analysis of Algorithms, Spring 2015. MIT. [2018-10-21]. （原始内容存档于2018-11-25）.