我有一個未加權的連接圖 G，有 n 個頂點和 m 個邊。
m=O(n log n)。
我想找到從頂點 s 到頂點 v 的最短路徑。
我想知道 BFS 遍歷或 Dijkstra 演算法是否會漸近更快。
BFS 將從 s 開始。Dijkstra 的演算法，從 s 開始，并實作了一個斐波那契堆。
BFS 的運行時間為 Θ(n m) = O(n n log n) = O(n log n)
而 Dijkstra 的運行時間為 O(m n log n) = O(n log n n log n) = O(n log n)
那么對于這個問題，這兩種演算法都是漸近式的，還是我遺漏了什么？
uj5u.com熱心網友回復：
對于未加權圖的給定屬性：
- ??(??,??) 是連通的，并且
- |??| ∈ θ(|??|log|??|)
...我們確實可以為 BFS 和帶有斐波那契堆的 Dijkstra 演算法推匯出 ??(|??|) 的時間復雜度。
只是一個補充說明：
短語“漸近一樣快”并不意味著有一個輸入大小，高于該大小，兩種演算法都將運行得一樣快。這意味著對于足夠大的輸入，其運行時間的比率（在同一臺計算機上）將保持在恒定的最小/最大范圍內。
由于斐波那契堆有相當多的開銷，而 BFS 只需要一個簡單的佇列或兩個陣列，毫無疑問，這個有界比率將有利于 BFS。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335904.html
上一篇：字典序最小字串的排列數