高级算法设计与分析 学习笔记10 平摊分析
动态表，可以变长。
一溢出就另起一个两倍大小的表。
可以轻易证明把n个数字放进去的时间复杂度是O(n)，n + n/2 + n/4……也就2n，插入数字本身也就是n，加起来最多不超过3n.
这种复杂度究竟是怎么算的？毕竟每次插入复杂度不一样，怎么算平均呢？
当然，计算平摊不只有这种方法：
银行法：
势能法：
把存款当成当前集合的势能。
首尾相连很多都被抵掉了。
使用势能法分析之前的动态表，怎么说？：
势能和存款就是一个意思。
问题：这些什么存款，势能的，一次多少究竟是怎么算出来的？
答曰：先用最开始的方法算出来总体的复杂度，然后凑。
原文地址：https://blog.csdn.net/LI_XIAO_XING/article/details/142638382
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！