算法的攤銷分析

Question

我正在閱讀攤銷分析。我無法完全理解它與我們執行的計算算法的平均或最差情況行爲的正常分析有何不同。有人可以用排序或其他的例子來解釋嗎？

Answer 1

攤銷分析給出了 中最差情況下每項操作的平均表現（隨時間變化）。

在一系列操作中，最糟糕的情況在每次操作中都不會經常發生 - 有些操作可能很便宜，有些操作可能很昂貴。因此，傳統的最壞情況每次操作分析可能會給出過分悲觀的界限。例如，在動態數組中，只有一些插入需要線性時間，但其他插入需要一定的時間。

當不同的插頁需要不同的時間時，我們如何準確地計算總時間？攤銷方法將爲序列中的每個操作分配一個「人工成本」，稱爲操作的攤銷成本。它要求序列的總實際成本應該以所有操作的攤銷成本總額爲界。

請注意，在分攤攤銷成本時有時會有靈活性。 三種方法在平攤分析

1. 聚合方法（或蠻力）使用
2. 會計處理方法（或莊家的方法）
3. 電位法（或物理學家的方法）

對於實例假設我們正在對一個數組進行排序，在這個數組中，所有的鍵都是不同的（因爲這是最慢的情況，並且它們需要的時間與它們不是時間的時間相同，如果我們沒有對等於主鍵的鍵做任何特殊處理）。

快速排序選擇隨機數據透視。這個關鍵點同樣可能是最小的關鍵點，第二小的關鍵點，第三小的關鍵點......或最大的關鍵點。對於每個鍵， 的概率是1/n。假設T（n）是一個隨機變量，它等於在不同密鑰上的快速排序的運行時間。假設快速排序選擇第i個最小的鍵作爲關鍵點。然後我們在長度爲i - 1的列表上遞歸地運行quicksort，並在長度爲n - i的列表上長度爲 。這需要O（n）的時間來劃分並連接所有的名單，讓我們 說至多n美元，使運行的時間是

在這裏，我是一個隨機變量，它可以是任何數量從1（樞軸是 最小鍵）至n（樞軸是最大鍵），每個的概率是1/n的選擇，所以

該方程被稱爲復發。重複的基本情況是T（0）= 1和T（1）= 1。這意味着排序長度爲零或1的列表最多花費1美元（時間單位）。

所以，當你解決：

表達式1 + 8J log_2Ĵ可能被高估，但它不是做 問題。重要的是，這證明E [T（n）]在O（n log n）中。 換句話說，快速排序的預期運行時間是O（n log n）。

此外，攤銷運行時間 與預計運行時間之間存在細微但重要的差異。具有隨機樞軸的快速排序需要O（n log n）預期運行時間，但其最壞情況運行時間在Θ（n^2）中。這意味着存在一個很小的可能性，即快速排序會花費（n^2）美元，但是隨着n增長，發生這種情況的可能性接近於零。

快速排序爲O（n log n）的預期時間
QuickselectΘ（n）的預計時間

對於數字示例：

的基於比較的排序下界是：

最後，你可以找到更多信息有關快速排序的平均案例分析here

Answer 2

平均 - 概率分析，平均是相對於所有可能的輸入，它的估計算法的可能運行時間。

攤銷 - 非概率分析，與一批調用算法相關計算。

例子 - 活力大小的堆棧：

說，我們定義了一些大小的堆棧，每當我們使用最多的空間，我們分配兩次老大小和元素複製到新的位置。

整體我們的成本是：

• O（1）每次插入\缺失

• ø每次插入（分配和複製）（n）的即使堆棧滿

所以現在我們問，插入需要多少時間？

可能會說O（n^2），但是我們不會爲每個插入付O（n）。 所以我們是悲觀的，正確的答案是O（n）的時間對於n插入，讓我們看看爲什麼：

可以說，我們先從數組的大小= 1

忽略複製我們將支付爲O（n ）每插入一次。

現在，我們能做的只有當棧有這些數量的元素的完整副本：

1,2,4,8，...，N/2，N

對於這些（1 + 2 + 4 + 8 + ... + n/4 + n/2 + n）= const *（n（n） + 1/2 + 1/4 + 1/8 + ...）

其中， （1 + 1/2 + 1/4 + 1/8 + ...）= 2

所以我們支付O（n）的所有複製+ O（n）的實際n插入

O（n）n操作的最壞情況 - > O（1）每次操作攤銷。