作者NOtWorThy ()
看板Grad-ProbAsk
標題[理工] [資結] -圖行表示法
時間Mon Oct 26 15:25:52 2009
圖行表示法 採用 鄰接串列
書上說 trace 圖有幾個邊 的時間複雜度是O(n+e)
為啥不是O(n*e)? 每個點不都是O(e)嗎? 那n個點不就是O(n*e)?
請問如何思考?
謝謝!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.37.196
1F：推 FRAXIS:總共也只有|E|條邊阿 所以怎麼trace都只會花O(|E|)的時間 10/26 22:12
2F：推 polomoss:再加上左邊node標頭有N個，所以O(N+E) 10/27 19:03