合併操作的攤銷成本

計算合併操作的攤銷成本是一項艱鉅的任務。最大的困難在於根據隨機的操作序列中不同操作成本的差異進行累加。雖然我們的設計目標會受到操作序列成本的影響，但根據操作序列成本定義操作攤銷成本的概念卻沒有任何幫助。透過實現一個潛在函式來抵消實際成本的差異是處理這種情況的一種完美方式。在下一主題中，我們討論攤銷成本的概念。

令 B 是基本運算 P = {P₁, P₂,……, P_k} 的抽象資料型別 (ADT)，令 DS 是實現 B 的資料結構。令 F 是指定在資料結構配置到非負實數的潛在函式。進一步令 F(Φ) = 0。令 DS^j 指定我們針對配置 DS 執行操作 Pk 而獲取的配置，令 C 表示針對 DS 執行 Pk 的實際成本。

然後，Pk 在 DS 上執行的攤銷成本表示為 a(Pk, DS)，由下式給出

a(P_k, DS) = C + F(DS^j) – F (DS)

如果對所有大小為 m 的配置 DS，a(P_k, DS)≤ cjg(m)，則我們得出 Pk 的攤銷成本為 O(g(m))。

阿納布·查克拉博蒂

更新時間：2020 年 1 月 2 日

282 次檢視

開啟您的 職業生涯

完成課程獲得認證

開始