平攤分析

平攤分析（英語：Amortized analysis）在電腦科學中，是用於演算法分析中的方法，平攤分析常用於分析資料結構（動態的資料結構），在使用平攤分析前須知道資料結構各種操作所可能發生的時間，並計算出最壞情況下的操作情況並加以平均，得到操作的平均耗費時間。平攤分析只能確保最壞情況效能的每次操作耗費的平均時間，並不能確認平均情況效能。

一個簡單的例子，一個長度為 $n$ 的list，在list的最後要加入一筆新的資料此時要花費的操作時間為 $O(n)$，此時也是加入新的資料的最糟糕的情況。但是，一個 $n$ 個插入的操作序列仍然可以在 $O(n)$ 的時間內完成，因為剩下的插入可以在常數時間內完成，因此 $n$ 個插入可以在 $O(n)$ 的時間內完成。因此每操作的平攤耗費為 $O(n)/n=O(1)$。

注意平攤分析與平均時間分析和概率演算法的概率分析不同。在平均時間分析中，我們平均化所有可能的輸入；在概率演算法的概率分析中，我們平均化所有可能的隨機選擇；在平攤分析中，我們平均化一系列操作的耗費。平攤分析假設的是最壞情況輸入並且通常不執行隨機選擇。

平攤分析中幾種常用的技術:

• 聚合分析決定 $n$ 個操作序列的耗費上界 $T(n)$，然後計算平均耗費為 $T(n)/n$。
• 記賬方法確定每個操作的耗費，結合它的直接執行時間及它在對執行時中未來操作的影響。通常來說，許多短操作增量累加成「債」，而通過減少長操作的次數來「償還」。
• 勢能方法類似記賬方法，但通過預先儲蓄「勢能」而在需要的時候釋放。

平攤分析種類

聚集法(Aggregate method)

計算n個操作的時間複雜度上限T(n) 平攤T(n)至每一個操作，每一個操作的平攤成本是T(n)/n

記帳法(Accounting method)

執行花費較低的operations時先存credit未雨綢繆, 供未來花費較高的operations使用

對每個操作定義一個合法的平攤成本(amortized cost) 假設$c_{i}$為第i個操作的actual cost，${\hat {c_{i}}}$為第i個操作的amortized cost

若$c_{i}<{\hat {c_{i}}}$，則credit=${\hat {c_{i}}}-c_{i}$，我們把credit存起來(deposited)，未來可以提取(withdraw) 若$c_{i}>{\hat {c_{i}}}$，則提取credit

設置每個操作的平攤成本(amortized cost)後，要做valid check確保credit不可以是0，也就是說 $\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$

位能法(Potential method)

定義一個位能函數(potential function)$\Phi (D)$，將資料結構D(例如: 堆疊)的狀態對應到一個實數

$D_{0}$: 資料結構D的初始狀態

$D_{i}$: 資料結構D經過$i$個操作後的狀態

$c_{i}$: 第$i$個操作的actual cost

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

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

$\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})$

為了滿足$\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$

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

例子

堆疊(stack)的平攤分析

我們定義一個堆疊有下列操作

操作(operation)	說明	actual cost
S.push(x)	將一個元素x放入堆疊S中	$O(1)$
S.pop()	把堆疊S中最上面的元素取出	$O(1)$
S.multi-pop(k)	一次pop 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

接下來我們分別使用聚集法(aggregate method), 記帳法(Accounting method), 位能法(Potential method)求出"堆疊一個操作的平攤成本是O(1)"

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

令$n_{push}$是S.push(x)的執行次數，$n_{pop}$是S.pop()的執行次數，$n_{multi-pop}$是S.multi-pop(k)的執行次數

$n=n_{push}+n_{pop}+n_{multi-pop}$為總執行次數

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

因為一個堆疊S如果是空的，就不能執行pop了，也就是說可以pop或multi-pop的元素個數不會超過S中push進去的元素個數

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

假設$T(n)$是執行$n$個操作的時間複雜度上限

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

所以堆疊一個操作的平攤成本為$O(n)/n=O(1)$

使用記帳法(Accouting method)分析堆疊操作的平攤成本

我們假設S.push(x), S.pop(), S.multi-pop(k)的amortized cost分別為2, 0, 0，如下表所示

操作(operation)	actual cost $c_{i}$	amortized cost ${\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

Valid Check 證明: $\sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}$
${\color {Red}proof:}$ push進入堆疊S的元素會存入credit $1 pop(S), multi-pop(S, k) 會取出這些元素的credit $1

因此每個操作的平攤成本是O(1)

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

我們定義位能函數$\Phi (D)$為執行i個操作後，堆疊內的元素個數

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

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

計算堆疊S每一個操作的平攤成本

操作(operation)	平攤成本(amortized cost) ${\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-1\right\vert )-\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-k\right\vert )-\left\vert S\right\vert =k-k=0$

總平攤成本 $\sum _{k=1}^{n}{\hat {c_{i}}}=2\times n_{push}=O(n)$，所以堆疊單一個操作的平攤成本是$O(n)/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)$。

通常用法

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