摊余分析\n

摊余分析

当出现较慢的偶尔执行的操作时使用这种分析方法，而大多数快速执行的操作却非常频繁。我们需要摊余分析的数据结构包括哈希表、不相交集合等。

在哈希表中，搜索的时间复杂度通常为 O(1)，但有时会执行 O(n) 操作。当我们想在哈希表中搜索或插入元素时，大多数情况下，这是项常量时间任务，但当发生冲突时，需要 O(n) 次操作来解决冲突。

聚合方法

聚合方法用来查找总成本。如果我们想添加一堆数据，则需要通过此公式找出摊余成本。

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

摊余分析示例

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

对于动态数组，令 第 i 次插入的成本为。

Ankith Reddy

更新日期： 2020 年 6 月 17 日

17K+ 浏览量

开启您的事业

完成课程并获得认证

开始