問題タブ [fibonacci-heap]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
74 問題
0
投票する
1
に答える
1004
参照
algorithm - フィボナッチ ヒープを使用した Prim のアルゴリズム: なぜ O(E + V*log(V)) なのか?
Prim のアルゴリズムとその実装方法を知っています。また、その時間計算量が O(E + V log(V)) である理由も認識しています。
エッジを E 回 (つまり O(E) で) 追加し、最小の V 回 (つまり O(V*log(V)) を選択します。しかし、私はその一部を理解していません: なぜ V 回?! 私は知っていますツリーには V-1 エッジがありますが、最も重いエッジが MST にある必要がある場合は、V 時間ではなく、最小の E 時間を選択する必要があります。
例: 各エッジの重みが 1 の完全なグラフ。ただし、接続されているすべてのエッジの重みが 10^18 である 1 つの頂点を除きます。