摊余成本复杂度

摊余分析

在偶尔的操作非常慢，但大多数执行非常频繁的操作更快时，会使用此分析。在数据结构中，我们需要散列表、不相交集等摊余分析。

在散列表中，搜索时间复杂度大多数时候是 O(1)，但有时它执行 O(n) 操作。当我们希望在散列表中搜索或插入元素时，在大多数情况下需要花固定时间完成任务，但当发生冲突时，它需要执行 O(n) 次操作才能解决冲突。

聚集方法

聚集方法用于找到总成本。如果我们要添加很多数据，那么我们需要通过此公式找到摊余成本。

对于 n 个操作的序列，成本为 -

摊余分析示例

对于动态数组，可以在给定的索引处以 O(1) 的时间插入项。但是，如果数组中不存在该索引，则无法以固定时间执行任务。对于这种情况，它最初将数组大小加倍，然后在索引存在的情况下插入元素。

对于动态数组，令 𝑐𝑖 = 第 𝑖 次插入的代价。

Arnab Chakraborty

更新于: 2019 年 8 月 5 日

3K+ 浏览

开启你的 职业生涯

完成课程并获得认证

开始