[理工] 資結 adjacency list

看板Grad-ProbAsk作者時間8年前 (2017/08/22 14:21), 編輯推噓0(0推 0噓 6→)
留言6則, 2人參與, 最新討論串1/1
請問資結第六章圖論中 在使用adjacency list之下 計算圖形的邊數 http://i.imgur.com/hM0uCq2.jpg
http://i.imgur.com/oYiXswy.jpg
時間複雜度為什麼是O(n+e)? 我直觀感覺是每回做O(e)次乘上n個點=O(n*e)... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1503382887.A.B34.html
→
08/22 15:07, , 1F
List只有記錄他有的邊 n*e是martrix 要整個掃過才知道
08/22 15:07, 1F
→
08/22 15:08, , 2F
應該說list只有記錄該V的edge
08/22 15:08, 2F
→
08/22 15:15, , 3F
請問我想成是進入n個vertex串列首=O(n), 掃描所有Node是
08/22 15:15, 3F
→
08/22 15:15, , 4F
O(e)。是這樣嗎
08/22 15:15, 4F
→
08/22 15:29, , 5F
4
08/22 15:29, 5F
→
08/22 15:33, , 6F
感謝><
08/22 15:33, 6F
‣ 更多 king8313 的文章
文章代碼(AID): #1Pcyrdiq (Grad-ProbAsk)