数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学数据结构中的均摊时间复杂度
均摊分析
当偶尔的操作非常慢，但大多数频繁执行的操作速度很快时，可以使用这种分析方法。在数据结构中，我们需要对哈希表、不相交集等进行均摊分析。
在哈希表中，大多数情况下搜索时间复杂度为 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}$$
更新于：2019年8月27日
895 次浏览
广告