作者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