1
爲什麼在Floyd-Warshall算法中存儲
？如果使用鏈表而不是N×N矩陣，那麼它不會少於嗎？關於Floyd-Warshall算法的O（n^2）存儲
A
回答
1
該鏈表的最壞情況的大小仍然是O(n^2)（我認爲？我不完全確定我瞭解你是如何使用它的），但查找代價將會足夠昂貴以改變漸近複雜性（在鏈表上的操作與在已知大小的矩陣上的操作不具有相同的複雜度）。
相關問題
- 1. 列表中列表的查找算法優於O（n2）複雜性
- 2. 關於緩存算法
- 3. Big-O算法
- 4. O（logn）時間和算法關係
- 5. 關於adaboost算法
- 6. 關於Apriori算法
- 7. heapify O（n）算法
- 8. 算法的大O符號
- 9. 算法的大O分析？
- 10. 未知算法的大O
- 11. 關於hg子存儲庫
- 12. 關於HTML5離線存儲
- 13. 關於存儲多個值
- 14. 算法分析（big-O）算法
- 15. 如何計算動態規劃（Memoization）算法的大O O
- 16. 調度算法存儲
- 17. 如何查找O（n1 + n2）中的鏈表和BST的交集？
- 18. 關於與迴文相關的算法
- 19. 關於g ++ -O選項
- 20. Android O關於ActivityManager.html＃getRunningServices（int）
- 21. 關於壓縮算法
- 22. C++設置：存儲重複項：關於<運算符
- 23. 關於矢量內存存儲
- 24. 遞增算法 - O（tlgn）
- 25. O符號，決鬥算法
- 26. Big-O算法分析
- 27. 大O符號算法
- 28. 大O算法分析
- 29. 一個算法的大O表示法
- 30. 關於存儲的getchar（）的燒焦變
我對鏈接列表的建議是每個節點代表圖中的一個頂點。這樣你只能存儲圖中頂點的數量v + e次，而不是v^2次。我的算法教授說，將圖形存儲爲鏈表通常比以N×N矩陣更好，但我的觀點是查找成本太高而不是節省的空間。她的觀點是，如果你有十億個頂點，那麼節省的空間將是值得的。我認爲這不是真的。 –
鏈表是比較古怪的方式來存儲圖形。你的意思是存儲一個鄰接表？這是相當不同的。請記住，您仍然需要某個地方存儲所有權重，最壞的情況下是「（n-1）^ 2」值。 – Gian