电位法

根据计算复杂性理论,潜在方法定义为一种用于分析数据结构的分期偿还的时间和空间复杂性的方法,一种衡量其在一系列操作上的性能的方法,从而消除了不常见但昂贵的操作的成本。

在潜在方法中,选择函数Φ,该函数将数据结构的状态转换为非负数。如果将S视为数据结构的状态,则Φ(S)表示已在摊销分析中说明但尚未执行的工作。因此,可以将Φ(S)想象为计算在该状态下存储的势能量。在初始化数据结构之前,电位值定义为零。可替代地,可以将Φ(S)想象为代表状态S中的无序量或其与理想状态的距离。

示例

让我们可以表示满足以下属性的数据结构状态上的势函数Φ(读为“ Phi”)-

  • Φ(a0)= 0,其中a0是数据结构的起始状态。

  • 对于在计算过程中发生的数据结构中所有状态的Φ(at)≥0。

直观地,电位函数将能够在计算的任何时刻跟踪预充电时间。它测量可用的节省时间量,以支付昂贵的操作费用。就像银行家方法中的银行余额一样。但是有趣的是,它仅取决于数据结构的当前状态,无论使它进入该状态的计算历史如何。

然后,我们将工序的摊销时间定义为

c +Φ(a')-Φ(a),

其中c是操作的原始成本,a和a'分别是操作之前和之后的数据结构状态。因此,摊销时间定义为实际时间加上电势变化。理想情况下,应定义Φ,以使每次操作的摊销时间都较小。因此,对于低成本运营,潜力的变化应衡量为正,而对于高成本运营,则应衡量为负。