平攤分析(英語:Amortized analysis)在電腦科學中,是用於演算法分析中的方法,平攤分析常用於分析資料結構(動態的資料結構),在使用平攤分析前須知道資料結構各種操作所可能發生的時間,並計算出最壞情況下的操作情況並加以平均,得到操作的平均耗費時間。平攤分析只能確保最壞情況效能的每次操作耗費的平均時間,並不能確認平均情況效能。
一個簡單的例子,一個長度為
的list,在list的最後要加入一筆新的資料此時要花費的操作時間為
,此時也是加入新的資料的最糟糕的情況。但是,一個
個插入的操作序列仍然可以在
的時間內完成,因為剩下的插入可以在常數時間內完成,因此
個插入可以在
的時間內完成。因此每操作的平攤耗費為
。
注意平攤分析與平均時間分析和機率演算法的機率分析不同。在平均時間分析中,我們平均化所有可能的輸入;在機率演算法的機率分析中,我們平均化所有可能的隨機選擇;在平攤分析中,我們平均化一系列操作的耗費。平攤分析假設的是最壞情況輸入並且通常不執行隨機選擇。[1]
平攤分析中幾種常用的技術:
- 聚合分析決定
個操作序列的耗費上界
,然後計算平均耗費為
。[1]
- 記帳方法確定每個操作的耗費,結合它的直接執行時間及它在對執行時中未來操作的影響。通常來說,許多短操作增量累加成「債」,而通過減少長操作的次數來「償還」。[1]
- 勢能方法類似記帳方法,但通過預先儲蓄「勢能」而在需要的時候釋放。[1]
聚集法(Aggregate method)
[編輯]
計算n個操作的時間複雜度上限T(n)
平攤T(n)至每一個操作,每一個操作的平攤成本是T(n)/n
記帳法(Accounting method)
[編輯]
執行花費較低的operations時先存credit未雨綢繆, 供未來花費較高的operations使用
對每個操作定義一個合法的平攤成本(amortized cost)
假設
為第i個操作的actual cost,
為第i個操作的amortized cost
若
,則credit=
,我們把credit存起來(deposited),未來可以提取(withdraw)
若
,則提取credit
設定每個操作的平攤成本(amortized cost)後,要做valid check確保credit不可以是0,也就是說
位能法(Potential method)
[編輯]
定義一個位能函數(potential function)
,將資料結構D(例如: 堆疊)的狀態對應到一個實數
: 資料結構D的初始狀態
: 資料結構D經過
個操作後的狀態
: 第
個操作的actual cost
: 第
個操作的amortized cost
定義
為了滿足
我們定義
, 通常令
和
我們定義一個堆疊有下列操作
操作(operation) |
說明 |
actual cost
|
S.push(x) |
將一個元素x放入堆疊S中 |
|
S.pop() |
把堆疊S中最上面的元素取出 |
|
S.multi-pop(k) |
一次pop 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)分析堆疊操作的平攤成本
[編輯]
令
是S.push(x)的執行次數,
是S.pop()的執行次數,
是S.multi-pop(k)的執行次數
為總執行次數
操作(operation) |
actual cost |
執行次數
|
S.push(x) |
![{\displaystyle O(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21) |
|
S.pop() |
![{\displaystyle O(1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21) |
|
S.multi-pop(k) |
![{\displaystyle O(\min(\left\vert S\right\vert ,k))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd0b7560fd25b1314436a3922f3dfea26b46db56) |
|
因為一個堆疊S如果是空的,就不能執行pop了,也就是說可以pop或multi-pop的元素個數不會超過S中push進去的元素個數
所以
假設
是執行
個操作的時間複雜度上限
![{\displaystyle T(n)=O(1)\times n_{push}+O(1)\times n_{push}=O(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c20c2c9b484030f55e1e31b1c8d06076b828d4bf)
所以堆疊一個操作的平攤成本為
使用記帳法(Accouting method)分析堆疊操作的平攤成本
[編輯]
我們假設S.push(x), S.pop(), S.multi-pop(k)的amortized cost分別為2, 0, 0,如下表所示
操作(operation) |
actual cost ![{\displaystyle c_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01acb7953ba52c2aa44264b5d0f8fd223aa178a2) |
amortized cost
|
S.push(x) |
1 |
2
|
S.pop() |
1 |
0
|
S.multi-pop(k) |
![{\displaystyle O(\min(\left\vert S\right\vert ,k))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd0b7560fd25b1314436a3922f3dfea26b46db56) |
0
|
Valid Check
- 證明:
![{\displaystyle \sum _{k=1}^{n}{\hat {c_{i}}}\geq \sum _{k=1}^{n}c_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56228c6be85dace676a2d35ad069ce658975d517)
|
- push進入堆疊S的元素會存入credit $1
- pop(S), multi-pop(S, k) 會取出這些元素的credit $1
|
因此每個操作的平攤成本是O(1)
使用位能法(potential method)分析堆疊操作的平攤成本
[編輯]
我們定義位能函數
為執行i個操作後,堆疊內的元素個數
,因為堆疊一開始是空的
,因為堆疊的元素個數一定![{\displaystyle \geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da05245eb4e91f2f05daa9f0c42fd48975f9a690)
計算堆疊S每一個操作的平攤成本
操作(operation) |
平攤成本(amortized cost)
|
S.push(x) |
|
S.pop() |
|
S.multi-pop(k) |
|
總平攤成本
,所以堆疊單一個操作的平攤成本是
動態陣列的平攤分析
考慮一個隨元素個數增加而增長的動態陣列,比如Java的ArrayList或者C++的std::vector。如果我們的陣列大小從4開始,那麼來向其中增加四個元素的時間就是一個常數。然而,若要將第五個元素加入其中,那麼會花費更多時間,因為我們此時必須要建立一個兩倍於當前陣列大小的陣列(8個元素),把老元素拷貝到新陣列中,然後增加一個新元素。接下來的三次加入操作也同樣會花費常數時間,然後在陣列被填滿後則又需要一輪新的加倍擴充。
一般地,如果我們考慮任意一個任意的n大小的陣列並對其進行n + 1次加入操作。我們注意到,所有的加入操作都是常數時間的,除了最後一個,它會花費
時間在大小加倍上。因為我們進行了n + 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需要
時間將所有元素從輸入數組添加到輸出數組中,其中n是輸入數組的當前長度。 從輸入複製n元素後,我們可以在輸出數組再次為空之前執行n出隊操作,每次操作都需要一個恆定的時間。 因此,我們可以僅在
時間執行一系列n出列操作,這意味著每個出列操作的攤銷時間是
。[2]
或者,我們可以收取將任何項目從輸入數組複製到輸出數組的成本,以及該項目的早期排隊操作。 該計費方案將入隊的攤還時間加倍,但將出列的攤還時間減少到
。
- 在常見場合,我們把能很好平攤分析的演算法稱為「平攤演算法」。
- 線上演算法通常使用平攤分析。
[3]
- ^ 1.0 1.1 1.2 1.3 1.4 Kozen, Dexter. CS 3110 Lecture 20: Amortized Analysis. Cornell University. Spring 2011 [14 March 2015]. (原始內容存檔於2018-10-03).
- ^ Grossman, Dan. CSE332:Data Abstractions (PDF). cs.washington.edu. [2015年3月14日]. (原始內容存檔 (PDF)於2015年4月2日).
- ^ MIT 6.046J Design and Analysis of Algorithms, Spring 2015. MIT. [2018-10-21]. (原始內容存檔於2018-11-25).