何时使用均摊时间复杂度分析，何时使用平均时间复杂度分析呢？

Question

均摊时间复杂度虽然也是一种特殊的平均时间复杂度，但总归有区别。请问bobobo老师：什么情况下使用均摊，什么情况下使用平均呢？

Answer 1

liuyubobobo 2019-01-29 23:34:24

我们通常所说的复杂度，都是最坏复杂度。比如线性查找算法复杂度是O(n)的，是指最坏的情况下需要查找n个元素。（这么表述不够严谨，但是体会一下思想。）虽然有可能我们要查找的元素第一次就找到了。但是我们不能说线性扫描的复杂度是O(1)的。

均摊复杂度可以看做是最坏复杂度的一个补充。我们的add算法按照最坏复杂度看也是O(n)的，因为一旦触及resize就需要进行一次线性扫描。

但问题在于：根据我们设计的算法，resize不会每一次都触发。体会一下，这是和线性扫描本质的区别。线性扫描我们可以很容易的做出一组数据让“每一次”都需要查找n个元素。但是我们的这个add算法是“不可能每次”都触发resize的。所以说他是O(n)有些“冤枉”，虽然从最坏复杂度的定义角度，确实是O(n)。那怎么表示他并不是每次都是O(n)的呢？我们用均摊复杂度分析做一个补充说明。虽然他最坏的情况是O(n)，但是均摊来看是O(1)的。所以平均来看他的性能是可以接受的。

正由于均摊复杂度是最坏复杂度的一个补充，所以其实很多教材根本不介绍均摊复杂度分析。在这里也先了解一下这个概念就好了。均摊复杂度当然有用，但确实出现的频次并不高。10个算法里可能大概也就有1个能用上均摊复杂度分析。

继续加油！：）

• 提问者 30K必胜 #1

  非常感谢！

Answer 2

提问者 30K必胜 2019-01-29 18:03:07

我明白一些了，当操作具有无规律性的时候，考虑使用平均时间复杂度，如find操作；而当操作具有规律性的时候，考虑均摊复杂度，比如add操作。