我知道 Dijkstra 演算法的步驟順序是這樣的：
- 初始化 arr
min_distance，將 source 設為 0，其他設為 MAX_VALUE - 選擇不在
visited集合中的最小距離 - 將頂點放入
visited集合 - 遍歷鏈接到不在
visited集合中的所選頂點的所有邊 - 更新所有最小距離
- 繼續這樣做，直到我們得到目標頂點或無法選擇其他頂點
到目前為止，我已經看到了 2 種型別的實作，一種使用最小堆 O(log V) 來獲取最小頂點，另一種使用簡單回圈 (O(V))。
我的問題是，如果我們使用最小堆，它表示時間復雜度將為 O(E log V)，E 可以寫為 V^2。沒有它，我們可以獲得 O(V^2) 時間復雜度。為什么使用最小堆時時間復雜度看起來更糟？
uj5u.com熱心網友回復：
為什么使用最小堆時時間復雜度看起來更糟？
使用普通的二進制堆，情況會更糟。但前提是邊的數量很大。這就是為什么在維基百科上它說：
對于稀疏圖，即邊數遠少于 |V|2 的圖，Dijkstra 演算法可以通過以鄰接表的形式存盤圖并使用 [...] 優先級佇列來實作有效提取最小值來更有效地實作.
當使用可以提供 O(1) 減少鍵操作的堆（例如Fibonacci heap ）時，還可以將時間復雜度保持在 O(|V|2) 。再次參考同一篇文章：
對于自平衡二叉搜索樹或二叉堆，該演算法需要
Θ((|E| |V|)log|V|)
最壞情況下的時間[...]；對于連通圖，這個時間界限可以簡化為 Θ(|E|log|V|)。斐波那契堆將其改進為
Θ(|E| |V|log|V|)
...其中 -- 當 |E| = O(|V|2) -- 是 Θ(|V|2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/486304.html
上一篇：從盒子中取出物品的方法數