平摊分析

平摊分析，又称摊还分析（英語：Amortized analysis）是計算機科學中的一种算法分析方法，常用於分析資料結構（特别是動態的資料結構）的复杂性。

对于某些数据结构来说，其操作在某些情况下需要耗费相当大的运算资源，但大部分时候开销显著小于最坏情况。如果只使用最坏情况分析，可能会错误地低估其在实际使用时的效率。由于输入的类型、长度等因素都可能影响某一操作的开销，平摊分析通过考虑一组包含了各种不同操作的序列，将少数开销较大的操作平摊至整个序列上，从而得出一个更贴合算法实际应用时的复杂度。

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

历史

1985年，美国计算机科学家罗伯特·塔扬首先在他的论文中提出了聚集法（现已归为平摊分析中的一种方法）。他在文章中指出，有必要开发一种比一般概率分析更实用的分析方法。最初，平摊分析仅用于分析二叉树与并查集等少数几种算法。不过随着更多算法与数据结构的开发，平摊分析已经成为了一种计算机科学家普遍使用的分析方法。

平摊分析種類

在进行平摊分析前，首先要确认哪些操作序列是有可能出现的。对于数据结构这种具有持续性状态的算法来说，执行一次开销很大的操作可能会使得其进入一种不再可能执行大开销操作的状态。而再次执行这种大开销的操作之前，数据结构必须执行多次小开销的操作。平摊分析的思想就是将这些不频繁的大开销“平摊”至许多小开销上，从而得出更“平滑”的算法复杂性。

平摊分析主要有三种方法：聚集法、记账法和位能法。三种方法所得出的结果都是等价的。具体使用哪种方法应根据具体问题的性质，选择最简便的方法。

聚集法

聚集法（英語：Aggregate method）通过证明每个长度为n的操作序列所需的时间总和不超过一个上限函数T(n)，然后将T(n)平摊至每一個操作，每一個操作的平攤成本就是T(n)/n。

記帳法

记账法（英語：Accounting method），又称“银行家的方法”（英語：Banker's method），本质是聚集法的一个变种。记账法设想存在一名会计，在算法执行每个操作时为其发放一定量的“积分”。執行花費較低的操作時，算法可以将超出本次操作实际需要的积分存入“账户”，在未来执行花费较高的操作时再取出积分，支付当次操作不足的部分。如果能证明算法在执行这一系列操作时永远不会“透支”，那么就可以证明会计每次发放的积分数量就不小于这个算法的平摊复杂性。

位能法

位能法，或势能法（英語：Potential method），又称“物理学家的方法”（英語：Physicist's method），通过定義一個非负的位能函數（英語：Potential function）$\Phi (D)$，将数据结构的每个状态映射到一个实数。该函数本质上是统计了记账法中每一步数据结构所剩余的余额，但其计算时只取决于数据结构的当前状态，不考虑某一步骤之前的操作历史。使用位能法时，每一步操作的平摊复杂性被理解为其 实际开销 + 位能的改变量。

例子

多重弹出堆疊

我們定義一個特殊的堆疊，其具有下列操作：

操作	說明	实际开销
S.push(x)	將一個元素x押入堆疊S中	$O(1)$
S.pop()	把堆疊最上面的元素弹出	$O(1)$
S.multi-pop(k)	一次弹出k個元素	$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

我们规定堆栈初始化时不含任何元素。

注意到，如果使用最坏情况分析n个操作的序列的复杂性会得出以下结论：n个操作中，堆栈中至多有$n$个元素；每次执行S.mult-pop(k)时的最坏复杂性是$n$，因此在多重弹出堆栈上执行n个操作的最坏复杂性是$O(n^{2})$。然而，显然这是不合理的，因为一次弹出k个元素需要至少先压入k个元素。

接下來我們分別使用聚集法、記帳法与位能分别证明"堆疊一個操作的平攤成本是$O(1)$"

使用聚集法证明

令$n_{push}$是所有S.push(x)操作的总开销，$n_{pop}$是所有S.pop()的总开销，$n_{multi-pop}$是所有S.multi-pop(k)的总开销。

注意到，堆栈中的元素个数永远为非负，且初始为空。因此，有$n_{pop}+n_{multi-pop}\leq n_{push}$。

假設$T(n)$是執行$n$個操作的時間複雜度，则其有如下上界：

$T(n)=n_{pop}+n_{multi-pop}+n_{push}\leq 2\cdot n_{push}\leq 2n=O(n)$

至此，可以证明在多重弹出堆疊上的任意n长度的操作序列的平攤成本為$O(n)/n=O(1)$。

使用記帳法证明

我們规定，为S.push(x)、S.pop()、S.multi-pop(k)的分别发放2、0、0个积分，如下表所示

操作	实际开销 $c_{i}$	发放积分 ${\hat {c_{i}}}$
S.push(x)	1	2
S.pop()	1	0
S.multi-pop(k)	$O(\min(\left\vert S\right\vert ,k))$	0

我们需要证明对于任意n长度的操作序列，其存款数永远为非负，即：

$\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$

注意到，每个元素在压入堆栈时获得2积分，本次操作消耗1积分的同时存入1积分，因此不论通过何种方法弹出时，一定可以取出压入时存入的1积分，因此存款始终为非负。

至此，可以证明在多重弹出堆疊上的任意n长度的操作序列的平攤成本為$O(1)$。

使用位能法证明

我們定義位能函數$\Phi (D_{i})$為執行i個操作後，堆疊內的元素個數。显然，$\Phi (D_{i})$是非负的：

$\Phi (D_{0})=0$ ，因為堆疊一開始是空的

$\Phi (D_{i})\geq 0$ ，因為堆疊的元素個數一定$\geq 0$

計算堆疊S每一個操作的平攤成本。假设 S 在状态$\Phi (D_{i})$时有$\left\vert S\right\vert$ 个元素：

操作	平攤成本 ${\hat {c_{i}}}$
S.push(x)	${\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()	${\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})=1+(\left\vert S\right\vert -1)-\left\vert S\right\vert =0$
S.multi-pop(k)	${\hat {c_{i}}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})=k+(\left\vert S\right\vert -k)-\left\vert S\right\vert =k-k=0$

可见每个操作的平攤成本都是$O(1)$，因此任意n长度的操作序列的平攤成本就是$O(1)$。

动态数组

动态数组的平摊分析

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

一般地，如果我们考虑任意一个任意的n大小的数组并对其进行n + 1次加入操作。我们注意到，所有的加入操作都是常数时间的，除了最后一个，它会花费$O(n)$时间在大小加倍上。因为我们进行了n + 1次加入操作，我们可以将数组加倍的时间平摊到所有的加入操作上，因此得到加入操作的平均时间是${\tfrac {nO(1)+O(n)}{n+1}}=O(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需要$O(n)$時間將所有元素從輸入數組添加到輸出數組中，其中n是輸入數組的當前長度。 從輸入複製n元素後，我們可以在輸出數組再次為空之前執行n出隊操作，每次操作都需要一個恆定的時間。 因此，我們可以僅在$o(n)$時間執行一系列n出列操作，這意味著每個出列操作的攤銷時間是$O(1)$ 。

或者，我們可以收取將任何項目從輸入數組複製到輸出數組的成本，以及該項目的早期排隊操作。 該計費方案將入隊的攤還時間加倍，但將出列的攤還時間減少到$O(1)$。

通常用法

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