作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 资料结构 BFS时间复杂度在DS跟ALGO之间
时间Fri Jun 28 09:52:52 2019
图为BFS在DS版本的演算法
https://i.imgur.com/urtXZ57.jpg
https://i.imgur.com/4iUqKgS.jpg
比较表
https://i.imgur.com/FVlF3ni.jpg
想问的是为什麽DS版本是O(e)
而Algo版本O(n+e)？
看上去DS版并没有将建立array初值需要的时间算进去，但是
for i=1 to n do
visited[i] = false
这段应该也要O(n)的时间，跟Algo版本设立初值的时间应该没有不同...？
为什麽不用算进去呢？
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.190.122 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1561686774.A.D4D.html
1F：→ mistel: 还有想请问一下 DS的考卷如果要写演算法可以写algo版本的06/28 11:20
2F：→ mistel: psesudo code吗？ 感谢板上大大们06/28 11:20
3F：推 kyuudonut: 你可以重新思考一下 Big-O 的定义，再来思考要不要加06/28 14:17
4F：→ kyuudonut: 回推文: 老话一句，说明清楚就好了。研究所考试没有06/28 14:18
5F：→ kyuudonut: 标准答案06/28 14:18
感谢楼上 但是如果这样思考的话Algo版本的BFS应该也只要写O(e)就好不是吗？因为e介於(
n-1)~n(n-1)/2之间
也就是O(e)应该介於O(n)~O(n*n)之间
这样O(n+e)并不会因为多个n而有所变化....？
因为我上课时在想为什麽这边要加起来，然後回家看原文书也没有说明为什麽要加起来...
请问我漏掉什麽东西？感谢！！
※ 编辑: mistel (114.136.190.122 台湾), 06/28/2019 15:06:09
※ 编辑: mistel (114.136.190.122 台湾), 06/28/2019 15:07:51
6F：→ mistel: 突然想到是不是Algo跟DS之间的时间复杂度定义不一样 ... 06/28 17:08
7F：推 kyuudonut: 我比较倾向於认为 O(V+E) 这样的 expression 透漏了较 06/28 17:39
8F：→ kyuudonut: 多资讯在里面，意即复杂度可能会由该两项变数所影响 06/28 17:40
9F：→ kyuudonut: 而且 e 真的介於那个范围吗? 有人说给定的 Graph 一定 06/28 17:43
10F：→ kyuudonut: 会连通? XD 06/28 17:43
11F：→ mistel: 你说的没错 应该不一定会连通才对QQ 那这样我可以理解了 06/28 18:34
12F：→ mistel: ，感谢你！！！ 06/28 18:34