[理工] 資結 adjacency list

[king8313 ()]

請問資結第六章圖論中
在使用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
→ fate201: List只有記錄他有的邊 n*e是martrix 要整個掃過才知道
→ fate201: 應該說list只有記錄該V的edge
→ king8313: 請問我想成是進入n個vertex串列首=O(n), 掃描所有Node是
→ king8313: O(e)。是這樣嗎
→ fate201: 4
→ king8313: 感謝><