作者:
mistel (Mistel)
2019-06-28 09:52:52圖為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版本設立初值的時間應該沒有不同...？
為什麼不用算進去呢？
感謝
作者:
mistel (Mistel)
2019-06-28 11:20:00還有想請問一下 DS的考卷如果要寫演算法可以寫algo版本的psesudo code嗎？ 感謝板上大大們
作者:
kyuudonut (善良è€ç™¾å§“)
2019-06-28 14:17:00妳可以重新思考一下 Big-O 的定義，再來思考要不要加回推文: 老話一句，說明清楚就好了。研究所考試沒有標準答案
作者:
mistel (Mistel)
2019-06-28 17:08:00突然想到是不是Algo跟DS之間的時間複雜度定義不一樣 ...
作者:
kyuudonut (善良è€ç™¾å§“)
2019-06-28 17:39:00我比較傾向於認為 O(V+E) 這樣的 expression 透漏了較多資訊在裡面，意即複雜度可能會由該兩項變數所影響而且 e 真的介於那個範圍嗎? 有人說給定的 Graph 一定會連通? XD
作者:
mistel (Mistel)
2019-06-28 18:34:00你說的沒錯 應該不一定會連通才對QQ 那這樣我可以理解了，感謝你！！！