[理工] [資結] -圖行表示法

[NOtWorThy ()]

圖行表示法 採用 鄰接串列

書上說 trace 圖有幾個邊 的時間複雜度是O(n+e)

為啥不是O(n*e)? 每個點不都是O(e)嗎? 那n個點不就是O(n*e)?

請問如何思考?

謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.37.196
推 FRAXIS:總共也只有|E|條邊阿 所以怎麼trace都只會花O(|E|)的時間
推 polomoss:再加上左邊node標頭有N個，所以O(N+E)