平攤分析
維基百科,自由的 encyclopedia
平攤分析(英語:Amortized analysis)在電腦科學中,是用於演算法分析中的方法,平攤分析常用於分析資料結構(動態的資料結構),在使用平攤分析前須知道資料結構各種操作所可能發生的時間,並計算出最壞情況下的操作情況並加以平均,得到操作的平均耗費時間。平攤分析只能確保最壞情況效能的每次操作耗費的平均時間,並不能確認平均情況效能。
一個簡單的例子,一個長度為 的list,在list的最後要加入一筆新的資料此時要花費的操作時間為 ,此時也是加入新的資料的最糟糕的情況。但是,一個 個插入的操作序列仍然可以在 的時間內完成,因為剩下的插入可以在常數時間內完成,因此 個插入可以在 的時間內完成。因此每操作的平攤耗費為 。
注意平攤分析與平均時間分析和機率演算法的機率分析不同。在平均時間分析中,我們平均化所有可能的輸入;在機率演算法的機率分析中,我們平均化所有可能的隨機選擇;在平攤分析中,我們平均化一系列操作的耗費。平攤分析假設的是最壞情況輸入並且通常不執行隨機選擇。[1]
平攤分析中幾種常用的技術: