爲什麼我們要對斐波納契堆進行攤銷分析？

Question

斐波那契堆所有操作分析均爲攤銷性質。爲什麼不能像二項式堆一樣進行正常分析？

Answer 1

在二項堆中，每個操作都保證以某種最差情況下的性能運行。插入永遠不會超過時間O（log n），合併永遠不會超過時間O（log n + log m）等等。因此，在分析二項堆的效率時，通常使用更多傳統的算法分析。

現在，這就是說，有二項式堆的幾個屬性，只有在進行攤銷分析時才變得明顯。例如，假設堆最初是空的，那麼連續n次插入二項堆的成本是多少？您可以證明，在這種情況下，插入的攤銷成本爲O（1），這意味着執行n次插入的總成本爲O（n）。從這個意義上講，在傳統分析的基礎上使用分期分析可以揭示出比最保守的最壞情況分析最初可能出現的數據結構更多的見解。

從某種意義上說，斐波那契堆最好以分期償付的方式進行分析，因爲儘管許多操作的最壞情況邊界確實不是很好（例如，刪除分鐘或減少鍵可能需要在最壞的情況下，時間爲Θ（n）），在任何一系列操作中，斐波那契堆都具有出色的攤銷性能。即使單個刪除分鐘可能花費Θ（n）時間，一系列m個刪除分鐘也不可能花費超過Θ（m log n）時間。

從另一個角度來說，斐波那契堆是專門設計用來在攤銷意義上而非最壞情況下有效的。它們最初是爲了加速Dijkstra和Prim的算法而發明的，其中所有重要的是在n節點堆上執行m個減鍵和n個刪除的總成本，並且因爲這是設計目標，所以設計者沒有嘗試在最壞的情況下使斐波納契堆有效。