フィボナッチ ヒープは減価償却という意味では効率的ですが、最悪の場合はどれくらい効率的でしょうか? 具体的には、n ノードのフィボナッチ ヒープに対するこれらの各操作の最悪の場合の時間計算量はどれくらいですか?
- 分を見つける
- 削除分
- 入れる
- キーを減らす
- マージ
3591 次
1 に答える
6
フィボナッチ ヒープでの最小検索操作には、常に最悪の場合の O(1) 時間がかかります。そのオブジェクトを直接指すポインターが常に維持されます。
最小削除のコストは、最悪の場合、時間 Θ(n) かかります。これを確認するには、空のヒープから始めて、一連の n 回の挿入を行うことを想像してください。各ノードは独自のツリーに格納され、delete-min ヒープを実行すると、これらすべてのオブジェクトが O(log n) ツリーに結合され、すべてのノードに少なくとも 1 回アクセスするには Θ(n) 作業が必要になります。
挿入のコストは最悪の場合 O(1) です。これは、単一のノードを作成してリストに追加するだけです。マージは、2 つのリストを接合するだけなので、同様に O(1) です。
最悪の場合の減少キーのコストは Θ(n) です。すべての要素が、n 個のマークされたノードのリンク リストで構成される単一のツリーに格納されている縮退フィボナッチ ヒープを構築することができます。一番下のノードでキーの減少を行うと、ツリーを n 個の独立したノードに変換するカスケード カットの実行がトリガーされます。
于 2016-03-11T02:51:26.603 に答える