作者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/m.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