攤餘分析\n

攤餘分析

當出現較慢的偶爾執行的操作時使用這種分析方法，而大多數快速執行的操作卻非常頻繁。我們需要攤餘分析的資料結構包括雜湊表、不相交集合等。

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

聚合方法

聚合方法用來查詢總成本。如果我們想新增一堆資料，則需要透過此公式找出攤餘成本。

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

攤餘分析示例

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

對於動態陣列，令 第 i 次插入的成本為。

Ankith Reddy

更新日期： 2020 年 6 月 17 日

17K+ 瀏覽量

開啟您的事業

完成課程並獲得認證

開始