势能法
势能法(Potential Method)是摊还分析中最通用的一种方法,通过定义势能函数来衡量系统的”能量状态”。
基本思想
定义一个势函数 ,将系统的状态映射为一个实数(势能值)。要求初始势能 所有状态的势能值。摊还代价定义为实际代价加上势能的变化量。
公式
- 摊还代价 = 实际代价 + 势差
- 势差 = (操作后状态) (操作前状态)
关键条件
势函数必须满足非负性,且初始势能最小。
势能法要求势函数是非递减的,这样才能保证总摊还代价 总实际代价。

链接到
- 上一个知识点:1.5 核算法
- 下一个知识点:无(本章最后一个知识点)