amortized-analysis - フィボナッチ ヒープの償却分析を行う理由

Question

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

Answer 1

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

とはいえ、償却分析を行った場合にのみ明らかになる二項ヒープの特性がいくつかあります。たとえば、ヒープが最初は空であると仮定すると、二項ヒープに n 回連続して挿入を行うコストはいくらになるでしょうか? この場合、挿入の償却コストは O(1) であることを示すことができます。これは、n 回の挿入を行う総コストが O(n) であることを意味します。その意味で、従来の分析に加えて償却分析を使用すると、より保守的な最悪のケースの分析から最初に得られるよりも、データ構造に関するより多くの洞察が明らかになります。

ある意味では、フィボナッチ ヒープは、償却された意味で分析するのが最適です。これは、多くの操作の最悪の場合の境界が実際にはそれほど大きくないためです (たとえば、delete-min または reduce-key には時間がかかる可能性があります Θ(n ) 最悪の場合)、フィボナッチ ヒープは、一連の操作全体で優れた償却パフォーマンスを発揮します。個々の削除分には Θ(n) の時間がかかる場合がありますが、一連の m 分の削除に Θ(m log n) 時間以上かかることは決してありません。

ただし、別の意味では、フィボナッチ ヒープは、最悪の場合の意味ではなく、償却された意味で効率的になるように特別に設計されています。それらは当初、ダイクストラとプリムのアルゴリズムを高速化するために発明されました。重要なのは、n ノード ヒープで m 個のキーの減少と n 個の削除を実行するための総コストであり、それが設計目標だったので、設計者は最悪の場合でもフィボナッチ ヒープを効率的にします。