势能法

势能法(Potential Method)是摊还分析中最通用的一种方法,通过定义势能函数来衡量系统的”能量状态”。

基本思想

定义一个势函数 ,将系统的状态映射为一个实数(势能值)。要求初始势能 所有状态的势能值。摊还代价定义为实际代价加上势能的变化量。

公式

  • 摊还代价 = 实际代价 + 势差
  • 势差 = (操作后状态) (操作前状态)

关键条件

势函数必须满足非负性,且初始势能最小。

势能法要求势函数是非递减的,这样才能保证总摊还代价 总实际代价。

链接到

  • 上一个知识点:1.5 核算法
  • 下一个知识点:无(本章最后一个知识点)