攤銷分析\n

攤銷分析

在偶爾出現的操作非常慢，而大多數執行非常頻繁的操作更快的情況下，使用此分析。我們需要攤銷分析的資料結構為雜湊表、分離集合等。

在雜湊表中，搜尋時間複雜度大多數時候為 O(1)，但有時它會執行 O(n) 操作。當我們想在雜湊表中搜索或插入一個元素時，大多數情況下，它會用常量時間執行任務，但當發生衝突時，它需要 O(n) 次操作來解決衝突。

聚合方法

聚合方法用於查詢總成本。如果我們要新增一組資料，那麼我們需要使用此公式找出攤銷成本。

對於 n 個操作的序列，成本為−

攤銷分析示例

對於一個動態陣列，可以在給定的下標中以 O(1) 時間插入項。但如果該下標不在陣列中，它就無法在常量時間內執行任務。對於這種情況，它最初將陣列大小加倍，然後在存在下標時插入該元素。

對於動態陣列，讓 c_i = 第 _i_ 次插入的成本。

Ankith Reddy

更新於：17-6-2020

17K+ 瀏覽次數

開始 事業

完成課程即可獲得認證

開始