首页 > 其他 > 详细

复杂度分析---平摊分析(Amortized Analysis)

时间:2020-02-05 00:06:58      阅读:81      评论:0      收藏:0      [点我收藏+]

平摊分析(Amortized Analysis)

参考链接:https://blog.csdn.net/Ying_Xu/article/details/51433497

1、聚类分析

2、记账方法

3、势能方法

技术分享图片

其中的公式Ci表示为执行当前操作需要的花销

push操作:势能增加1,操作花销为1,因此均摊花销为2

pop操作:势能减少1,操作花销为1,因此均摊花销为0

MULTIPop:势能减少-#pop,操作花销为#pop,因此均摊花销为0

技术分享图片

势能可以看做一个操作的危险程度,越高势能越高越危险,对应平摊分析为,一个操作带来了更大的开销的危险程度。

当插入完第4个数据到扩张后的表的时候,size为8,势能最小,危险程度最低为0;
当插入完第8个数据,表扩张前,势能最高危险程度最高为8,这个数据8意味着下次表扩张,需要将这8个数据重新插入一遍。

复杂度分析---平摊分析(Amortized Analysis)

原文:https://www.cnblogs.com/Stephanie-boke/p/12261920.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!