算法導論--平攤分析之聚集分析，算法導論--平攤

算法導論--平攤分析之聚集分析，算法導論--平攤

在平攤分析中，執行一系列數據結構操作所需要的時間是通過對執行的所有操作求平均而得出的。

平攤分析可以用來證明在一系列操作中，通過對所有操作求平均之後，即使其中單一的操作具有較大的代價，平均代價還是很小的。平攤分析與平均情況分析的不同之處在於它不牽涉到概率；平攤分析保證在最壞情況下，每個操作具有平均性能。

聚集分析

在聚集分析中，要證明對所有的n，由n個操作所構成的序列的總時間在最壞情況下為T(n)。因此，在最壞情況下，每個操作的平均代價（或稱平攤分析）為T(n)/n。請注意這個平攤代價對每個操作都是成立的，即使當序列中存在幾種類型的操作時也是一樣的。

棧操作

 在關於聚集分析的第一個例子中，我們要分析增加了一個新操作後的棧。有兩種基本的棧操作，每種操作的時間代價都是O(1)：

PUSH(S,x)：將對象x壓入棧S。

POP(S)：彈出S的棧頂返回彈出的對象。

因為這兩個操作的運行時間都為O(1)，故可以把每個操作的代價都視為1。因此，含n個PUSH和POP操作的序列的總代價為n，而這n個操作的實際運行時間就是O(n)。

現在我們增加一個棧操作MULTIPOP(S,k)，它的作用是彈出棧S的k個棧頂對象，或者，當棧包含少於k個對象時，彈出整個棧中的數據對象。

當MULTIPOP(S,s)對一個包含s個對象的棧操作時，運行時間是多少？實際的運行時間與實際執行的POP操作數成線性關系，因而只要按PUSH和POP具有抽象代價1來分析MULTIPOP就足夠了。while循環迭代的次數是從棧中彈出的對象個數min(s,k)。對循環的每次迭代，都要調用一次POP。因此，MULTIPOP的總代價是min(s,k)，而實際運行時間則為這個代價的一個線性函數。

現在來分析一個由n個PUSH，POP和MULTIPOP操作構成的序列，其作用於一個初始為空的棧。序列中一次MULTIPOP操作的最壞情況代價為O(n)，因為棧的大小至多為n。因此，任意棧操作的最壞情況時間就是O(n)，因此n個操作的序列的代價是O(n^2)，因為可能會有O(n)個MULTIPOP操作，每個的代價都是O(n)。雖然這一分析是正確的，但通過單獨地考慮每個操作的最壞情況代價而得到的O(n^2)結論卻是不夠緊確的。

利用聚集分析，我們可以獲得一個考慮到n個操作的整個序列的更好的上界。事實上，雖然一次MULTIPOP操作的代價可能較高，但當作用於一個初始為空的棧上時，任意一個包含n個PUSH，POP和MULTIPOP操作的序列其代價至多為O(n)。為什麼會是這樣呢？一個對象在每次被壓入棧後，至多被彈出一次。所以，在一個非空棧上，調用POP的次數（包括在MULTIPOP的調用）至多等於PUSH操作的次數，即至多為n。對任意的n值，包含n個PUSH，POP和MULTIPOP操作的序列的總時間為O(n)。每個操作的平均代價為O(n)/n=O(1)。在聚集分析中，我們把每個操作的平攤代價指派為平均代價。所以在這個例子中，三個棧操作的平攤代價都是O(1)。

我們再一次強調，雖然已經說明一個棧操作的平均代價和運行時間是O(1)，但沒有用到概率推理。實際上，我們給出的是一列n個操作的最壞情況界O(n)。用n除這個總代價可得每個操作的平均代價，亦即平攤代價。