高级算法设计与分析 学习笔记10 平摊分析

动态表，可以变长。

一溢出就另起一个两倍大小的表。

可以轻易证明把n个数字放进去的时间复杂度是O(n)，n + n/2 + n/4……也就2n，插入数字本身也就是n，加起来最多不超过3n.

这种复杂度究竟是怎么算的？毕竟每次插入复杂度不一样，怎么算平均呢？

当然，计算平摊不只有这种方法：

银行法：

势能法：

把存款当成当前集合的势能。

首尾相连很多都被抵掉了。

使用势能法分析之前的动态表，怎么说？：

势能和存款就是一个意思。

问题：这些什么存款，势能的，一次多少究竟是怎么算出来的？

答曰：先用最开始的方法算出来总体的复杂度，然后凑。