Python - 均攤分析

均攤分析涉及估計程式中一系列操作的執行時間，而不考慮輸入值中資料分佈的範圍。一個簡單的例子是在排序列表中查詢值比在未排序列表中查詢值更快。

如果列表已經排序，那麼資料分佈如何並不重要。但當然，列表的長度會產生影響，因為它決定了演算法必須經歷的步驟數量才能獲得最終結果。

因此，我們看到，如果獲得排序列表的單個步驟的初始成本很高，那麼隨後查詢元素的步驟的成本就會大大降低。因此，均攤分析幫助我們找到一系列操作的最壞情況執行時間的界限。均攤分析有三種方法。

在相反的情況下，它將是負信用額度。為了跟蹤這些累積的信用額度，我們使用棧或樹資料結構。早期執行的操作（如排序列表）具有較高的均攤成本，但順序較晚的操作具有較低的均攤成本，因為利用了累積的信用額度。因此，均攤成本是實際成本的上限。

勢能方法 - 在這種方法中，儲存的信用額度被用作資料結構狀態的數學函式，用於未來的操作。數學函式的評估和均攤成本應該相等。因此，當實際成本大於均攤成本時，勢能會下降，並將其用於未來的昂貴操作。
聚合分析 - 在這種方法中，我們估計 n 步總成本的上限。均攤成本是總成本與步數 (n) 的簡單除法。。

列印頁面