数据结构中的均摊时间复杂度

均摊分析

当偶尔的操作非常慢，但大多数频繁执行的操作速度很快时，可以使用这种分析方法。在数据结构中，我们需要对哈希表、不相交集等进行均摊分析。

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

聚合方法

聚合方法用于查找总成本。如果我们想添加一堆数据，则需要通过以下公式找到均摊成本。

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

$\frac{Cost ( n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (Expensive\:operations)}{n}$

均摊分析示例

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

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

$So\:ci=1+\begin{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \0, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:Otherwise\end{cases}$

$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{\lgroup n-1\rgroup}\rfloor} 2j}{n}=\frac{O\lgroup n\rgroup}{n}$$

Arnab Chakraborty

更新于：2019年8月27日

895 次浏览

开启你的职业生涯

完成课程获得认证

开始学习