算法導論 平攤分析

在計算機科學中，特别是算法分析中，平攤分析尋找在最壞情況下的操作序列中每操作的平均耗費時間。平攤分析隻保證最壞情況性能的每操作耗費時間，不涉及平均情況性能。

這個方法需要知道操作序列中可能發生的每個操作。通常應用在操作間存在狀态的資料結構中。基本思想是一個最壞情況操作會改變狀态進而不會在一段時間内再次出現，是以"平攤"它的耗費。

一個簡單的例子，在某個特定實作的動态數組中，我們在每次數組溢出時增長數組的長度至原來的兩倍。是以需要數組空間配置設定，在最壞情況下一個插入操作需要O(n)的時間。但是，一個 n 個插入的操作序列仍然可以在 O(n) 的時間内完成，因為剩下的插入可以在常數時間内完成，是以 n 個插入可以在 O(n) 的時間内完成。是以每操作的平攤耗費為O(n) / n = O(1)。

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

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

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

amortized analysis(平攤分析）

how large should a hash table be?

2個方面，

1.as large as possible搜尋快 time

2.as small as possible 節約存儲空間 space