攤餘成本複雜度

攤餘分析

在偶爾的操作非常慢，但大多數執行非常頻繁的操作更快時，會使用此分析。在資料結構中，我們需要散列表、不相交集等攤餘分析。

在散列表中，搜尋時間複雜度大多數時候是 O(1)，但有時它執行 O(n) 操作。當我們希望在散列表中搜索或插入元素時，在大多數情況下需要花固定時間完成任務，但當發生衝突時，它需要執行 O(n) 次操作才能解決衝突。

聚集方法

聚集方法用於找到總成本。如果我們要新增很多資料，那麼我們需要透過此公式找到攤餘成本。

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

攤餘分析示例

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

對於動態陣列，令 𝑐𝑖 = 第 𝑖 次插入的代價。

更新於: 2019 年 8 月 5 日

3K+ 瀏覽

開啟你的 職業生涯

完成課程並獲得認證

開始
廣告