[理工] 資料結構 BFS時間複雜度在DS跟ALGO之間

[mistel (Mistel)]

圖為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://www.ptt.cc/bbs/Grad-ProbAsk/M.1561686774.A.D4D.html
→ mistel: 還有想請問一下 DS的考卷如果要寫演算法可以寫algo版本的
→ mistel: psesudo code嗎？ 感謝板上大大們
推 kyuudonut: 妳可以重新思考一下 Big-O 的定義，再來思考要不要加
→ kyuudonut: 回推文: 老話一句，說明清楚就好了。研究所考試沒有
→ kyuudonut: 標準答案
感謝樓上 但是如果這樣思考的話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
→ mistel: 突然想到是不是Algo跟DS之間的時間複雜度定義不一樣 ...
推 kyuudonut: 我比較傾向於認為 O(V+E) 這樣的 expression 透漏了較
→ kyuudonut: 多資訊在裡面，意即複雜度可能會由該兩項變數所影響
→ kyuudonut: 而且 e 真的介於那個範圍嗎? 有人說給定的 Graph 一定
→ kyuudonut: 會連通? XD
→ mistel: 你說的沒錯 應該不一定會連通才對QQ 那這樣我可以理解了
→ mistel: ，感謝你！！！