均攤分析

均攤分析，又稱攤還分析（英語：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)$。

通常用法

• 在常見場合，我們把能很好均攤分析的演算法稱為「平攤演算法」。
• 線上演算法通常使用均攤分析。