[理工] 資料結構 BFS時間複雜度在DS跟ALGO之間
圖為BFS在DS版本的演算法
https://i.imgur.com/urtXZ57.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
→
06/28 11:20,
6年前
, 1F
06/28 11:20, 1F
→
06/28 11:20,
6年前
, 2F
06/28 11:20, 2F
推
06/28 14:17,
6年前
, 3F
06/28 14:17, 3F
→
06/28 14:18,
6年前
, 4F
06/28 14:18, 4F
→
06/28 14:18,
6年前
, 5F
06/28 14:18, 5F
感謝樓上 但是如果這樣思考的話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
→
06/28 17:08,
6年前
, 6F
06/28 17:08, 6F
推
06/28 17:39,
6年前
, 7F
06/28 17:39, 7F
→
06/28 17:40,
6年前
, 8F
06/28 17:40, 8F
→
06/28 17:43,
6年前
, 9F
06/28 17:43, 9F
→
06/28 17:43,
6年前
, 10F
06/28 17:43, 10F
→
06/28 18:34,
6年前
, 11F
06/28 18:34, 11F
→
06/28 18:34,
6年前
, 12F
06/28 18:34, 12F