BIG-O /大哦符號

我試圖計算下列算法的大O但我很困惑，需要一些幫助：BIG-O /大哦符號

Algorithm 1. DFS(G,n) 
Input: G- the graph 
     n- the current node 
1) Visit(n) 
2) Mark(n) 
3) For every edge nm (from n to m) in G do 
4)  If m is not marked then 
5)   Dfs(G,m) 
6)  End If 
7) End For 
Output: Depends on the purpose of the search...

我甚至不會開始說什麼，我（錯誤地）計算出解決方案。任何人都可以幫我解釋一下嗎？

謝謝。

編輯：顯然我的O(n+m)的計算是正確的......有人可以驗證這一點嗎？

編輯2：或者是O(|n|+|m|)？

來源

2011-05-06 MusTheDataGuy

不，你真的應該說你認爲這是家庭作業，沒有人會幫助，如果你至少沒有證明你是至關重要的。 – 2011-05-06 13:21:10

我認爲你應該從你的推理開始，我們會幫助你。不要爲此感到尷尬，最好是證明你已經嘗試過，否則我們會假設你讓我們爲你做你的功課:-)。 – 2011-05-06 13:22:05

@Justin我只想指出，這實際上是修訂而不是作業。因此，我決定嘗試通過我自己的選擇來計算這個算法的Big-O。但是，如果你絕對必須知道，那麼我計算它是O（n + m）。正如你所看到的，這是（幾乎肯定）不正確，因爲我沒有看到任何Big-O導致O（x + y）... @Mark我希望這證實了我的推理！ :-D – MusTheDataGuy 2011-05-06 13:24:48

它的代價是O（n + e），其中n是節點的數量，e是邊的數量。

來源

2011-05-06 13:26:53 Heisenbug

這看起來像是一個簡單的圖形DFS，嘗試做一些簡單的算法示例，並找出需要做多少次迭代，並查看它與輸入值的關係（n個節點，以及m個邊）

來源

2011-05-06 13:23:33

允許在所有節點G中

整合

線1和線2獲取在G中的每個節點稱爲一次;即O（N）其中N是節點的數目
對於G中的每個邊緣，行4被調用一次;即O（E），其中E是邊緣的數量。
第5行爲G中的每個節點調用一次（除了我們開始的節點）;即O（N）。

這使得計算O(N + E)其可自E >= N減少到O(E)。

這裏假設我們只是將步驟計數爲相等。在實踐中，我們不知道不同步驟的相對成本。當這些插入時，複雜性可能不同。

來源

2011-05-06 13:33:24

BIG-O /大哦符號

回答

相關問題