勢能法

根據計算複雜度理論，勢能法被定義為一種用於分析資料結構的攤還時間和空間複雜度的方法，它衡量的是資料結構在一系列操作中的效能，並消除了不常見但代價高昂的操作的成本。

在勢能法中，選擇一個函式 Φ（讀作“Phi”），它將資料結構的狀態轉換為非負數。如果將 S 視為資料結構的狀態，則 Φ(S) 表示在攤還分析中已計入但尚未執行的工作。因此，可以將 Φ(S) 想象為計算該狀態中儲存的勢能大小。在初始化資料結構之前，勢能值被定義為零。或者，可以將 Φ(S) 想象為表示狀態 S 中的無序程度或其與理想狀態的距離。

示例

假設我們可以表示一個在資料結構狀態上的勢能函式 Φ，它滿足以下性質：

• Φ(a0) = 0，其中 a0 是資料結構的起始狀態。
• Φ(at) ≥ 0，對於計算過程中發生的任何資料結構狀態 at 都成立。

直觀地說，勢能函式能夠在計算的任何時刻跟蹤預先支付的時間。它衡量的是可用於支付昂貴操作的已儲存時間的數量。它就像銀行家方法中的銀行賬戶餘額。但有趣的是，它只取決於資料結構的當前狀態，無論導致它進入該狀態的計算歷史如何。

然後我們將操作的攤還時間定義為

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

其中 c 是操作的原始成本，a 和 a' 分別是操作前後的資料結構狀態。因此，攤還時間被定義為實際時間加上勢能的變化。理想情況下，應定義 Φ 使得每個操作的攤還時間都很小。因此，勢能的變化應在低成本操作中衡量為正，在高成本操作中衡量為負。

Arnab Chakraborty

更新時間： 2020年1月2日

2K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始