平摊分析--势能法

势能法介绍

平摊分析中最常用的方法

根据整个数据结构的特点设计势函数，保证初始势函数为0，整个操作序列中势函数>=0（这个特点保证了平摊代价始终大于实际代价）

对每个操作类：平摊代价 = 实际代价 + 势差

对整体操作序列：总代价 = 总平摊代价 - 势差

势函数的设计特点：

• 每次操作对 数据结构 造成改变的部分(实际代价越大，改变越大)
• 每次进行大代价操作后，势函数降低
• 每次进行大代价操作前，势函数达到峰值

【栈操作】

• 问题定义：初始为空的栈上进行push，pop，multipop操作的代价分析
• 设计：

设计势函数为：栈中元素的个数

【二进制计数器】

• 问题定义：初始为0 的k位二进制计数器
• 设计

设计势函数为：计数器中1的个数

（1）设第 i 次操作将 t 位置0 ， 将 1 位置1

实际代价：t+1

势差：1-t

平摊代价：2

 【拓展】初始不为0的二进制计数器（从k计数到n+k）

方法：根据势能关系：总平摊代价 - 总实际代价 = 势差 

总代价 = 初始为0的总代价 - （φn -  φ0）= 2n - （φn -  φ0）

【动态表】

• 问题定义：初始为空的动态表进行 插入、删除两种操作

若表满，则将原表扩张一倍

若表的装载因子不足1/4时，则将原表收缩一半

• 使用聚集法 和 会计法 将不再赘述，在进行平摊分析时，我们优先使用势能法
• 势函数设计：

动态表的装载因子a始终在 [1/4，1] 之间，大代价操作前，装载因子a==1/4 或 1，大代价操作后，装载因子a==1/2

即1/4 和 1时势函数最大，1/2时势函数最小

综上，设计势函数：| a-1/2 | ~> | 2*num - size |

• 分析：

（1）第 i 次插入操作发生扩张（m - 2m）

实际代价：m+1

势差：2-m

平摊代价 = 3

（2）第 i 次插入操作未扩张

平摊代价 = 3

（3）第 i 次删除操作发生收缩（2m - m）

实际代价：m+1

势差：2 - m

平摊代价 = 3

（4）第 i 次删除操作未收缩

平摊代价 = 3

总代价：3n

平摊分析--势能法

原文：https://www.cnblogs.com/duanshuai/p/13172979.html