圖形搜索O（log（N）（N + M）

首先解釋一下：我在java中實現了一個包管理器模擬器，也就是隻輸出正確的東西但實際上沒有安裝任何東西的包管理器。問題是我需要搜索每個軟件包以及它的所有依賴關係，看看它們是否都安裝正確。我被告知有可能得到等於log（N）（N + M）的最壞情況運行時間，，其中N是包的數量，M是依賴的數量，我認爲這是某種BFS實現需要完成的，也許只是爲每個包做一個BFS，而且是依賴，所以如果我找到一個包已經通過一些其他軟件包的依賴性檢查過了，但它只是跳過了，但是在我的腦海中，似乎沒有正確的最壞情況運行時間圖形搜索O（log（N）（N + M）

有沒有人有任何想法如何實現獲得正確的運行時間？

來源

2014-11-06 Chairbench

對於每個包{是否安裝了所有的依賴關係}有什麼問題？ – Nemo 2014-11-06 01:48:31

這會工作，但運行時間將是O（N * M），這是很高的路。我需要它是O（log（N）（N + M）... – Chairbench 2014-11-06 02:28:57

爲什麼會是O（NM）？M是* total *依賴關係的數量，並且在平凡的方法中，您只檢查每個依賴關係一次...... – Nemo 2014-11-06 02:36:20

我認爲這可以通過拓撲排序來完成，通常是通過搭載DFS而不是BFS來完成的。那有一個線性時間O（M + N）。

來源

2015-02-11 18:27:40 mateor

圖形搜索O（log（N）（N + M）

回答

相關問題