[理工] [資結]-DFS

看板Grad-ProbAsk作者 (123)時間14年前 (2010/02/25 19:32), 編輯推噓3(3推 0噓 9→)
留言12則, 6人參與, 最新討論串1/1
The complexity for performing depth first search and breath first search on a n-vertex undirected graph which is represented by an adjacency list is O(n) 洪X解答說是false 所以答案為O(e+v)，但是偉X說是O(n^2)，網路上找說用list是O(2|v|) 那到底是哪一個＝ ＝?因為洪X的解答網路上的評價...所以每錯一題我就想問一下 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.138.105.159
→
02/25 19:36, , 1F
o+e
02/25 19:36, 1F
→
02/25 19:36, , 2F
更正 e+v
02/25 19:36, 2F
推
02/25 19:38, , 3F
用adjacency list O(v+e) , matrix O(v^2)
02/25 19:38, 3F
→
02/25 19:38, , 4F
2v也對...
02/25 19:38, 4F
→
02/25 19:44, , 5F
嗯 了解了
02/25 19:44, 5F
→
02/25 19:44, , 6F
跟三樓的一樣
02/25 19:44, 6F
→
02/25 19:47, , 7F
那既然2v也對為何他說O(N)不行..
02/25 19:47, 7F
→
02/25 20:02, , 8F
O(2|v|)就是O(2n)=O(n)阿＝ ＝ 可是解答說不對
02/25 20:02, 8F
→
02/25 22:01, , 9F
仔細看了一下我好像打錯了..應該是O(e)
02/25 22:01, 9F
→
02/25 22:02, , 10F
考慮link list數 2e -->O(e)不是O(n)
02/25 22:02, 10F
推
02/25 22:22, , 11F
e夠大就變成n^2了？
02/25 22:22, 11F
推
02/26 09:25, , 12F
樓上說的沒錯 但是一般圖論的演算法都是把e和v分開
02/26 09:25, 12F
‣ 更多 gn00618777 的文章
文章代碼(AID): #1BXb_dKF (Grad-ProbAsk)