フィボナッチヒープの償却分析はなぜですか？

Question

フィボナッチヒープでは、すべての操作分析のために、性質上償却されます。二項ヒープの場合のように、通常の分析ができないのはなぜですか？

Answer 1

バイナリヒープでは、各操作は特定の最悪の場合のパフォーマンスで動作することが保証されています。挿入は時間O（log n）を超えることはありません。マージは時間O（log n + log m）以上かかることはありません。したがって、二項ヒープの効率を分析する場合、従来のアルゴリズム分析。

ここで、償却分析を行うときにのみ明らかになる、2項ヒープのいくつかのプロパティがあります。たとえば、ヒープが最初は空であると仮定して、2項ヒープへの連続したn回の挿入のコストはいくらですか？この場合、償却された挿入コストはO（1）であり、n個の挿入を行う総コストはO（n）であることを示すことができます。その意味で、従来の分析の上で償却分析を使用すると、より慎重な最悪の場合の分析から最初に生じたよりも、データ構造についてのより多くの洞察が明らかになります。

フィボナッチヒープは、償却された意味で最もよく分析されます。なぜなら、多くの操作での最悪の場合の境界が実際にはそれほど大きくなくても（たとえば、削除最小または減少キー時間はΘ（最悪の場合））、フィボナッチヒープは一連の操作の間に優れた償却性能を有する。個々のdelete-minはΘ（n）時間かかるかもしれませんが、一連のm delete-minsがΘ（m log n）時間以上かかることは決してありません。

しかしフィボナッチヒープは、最悪の場合よりもむしろ償却された意味で効率的であるように特別に設計されています。彼らは最初にDijkstraとPrimのアルゴリズムをスピードアップするために考案されました。nノードヒープ上でm個の減少キーとn個の削除を実行するのに要したすべてのコストが設計上の目標であったため、設計者はフィボナッチヒープを最悪の場合に効率的にする。