势能法

根据计算复杂度理论，势能法被定义为一种用于分析数据结构的摊还时间和空间复杂度的方法，它衡量的是数据结构在一系列操作中的性能，并消除了不常见但代价高昂的操作的成本。

在势能法中，选择一个函数 Φ（读作“Phi”），它将数据结构的状态转换为非负数。如果将 S 视为数据结构的状态，则 Φ(S) 表示在摊还分析中已计入但尚未执行的工作。因此，可以将 Φ(S) 想象为计算该状态中存储的势能大小。在初始化数据结构之前，势能值被定义为零。或者，可以将 Φ(S) 想象为表示状态 S 中的无序程度或其与理想状态的距离。

示例

假设我们可以表示一个在数据结构状态上的势能函数 Φ，它满足以下性质：

• Φ(a0) = 0，其中 a0 是数据结构的起始状态。
• Φ(at) ≥ 0，对于计算过程中发生的任何数据结构状态 at 都成立。

直观地说，势能函数能够在计算的任何时刻跟踪预先支付的时间。它衡量的是可用于支付昂贵操作的已保存时间的数量。它就像银行家方法中的银行账户余额。但有趣的是，它只取决于数据结构的当前状态，无论导致它进入该状态的计算历史如何。

然后我们将操作的摊还时间定义为

c + Φ(a') − Φ(a)，

其中 c 是操作的原始成本，a 和 a' 分别是操作前后的数据结构状态。因此，摊还时间被定义为实际时间加上势能的变化。理想情况下，应定义 Φ 使得每个操作的摊还时间都很小。因此，势能的变化应在低成本操作中衡量为正，在高成本操作中衡量为负。

Arnab Chakraborty

更新时间： 2020年1月2日

2K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始