[理工] 105交大資演(25)

看板Grad-ProbAsk作者 (PTT領導)時間7年前 (2017/01/18 15:32), 編輯推噓6(6推 0噓 21→)
留言27則, 3人參與, 最新討論串1/1
http://imgur.com/a/Pt0pN 想請問這題 BFS DFS 要怎麼做出 equivalence classes 然後 (b) (c) 各錯在哪裡呢 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.14.64 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484724776.A.7B8.html
推
01/18 15:41, , 1F
(b)我在想DFS和BFS的time complexity都是O(V+E)，應該
01/18 15:41, 1F
→
01/18 15:42, , 2F
差不多快？
01/18 15:42, 2F
→
01/18 15:44, , 3F
BFS可以拿來找connected component，每個connected
01/18 15:44, 3F
→
01/18 15:45, , 4F
component就當作是一個disjoint set，一個disjoint
01/18 15:45, 4F
→
01/18 15:45, , 5F
set就視為一個equivalence class，阿Union/Find也是可
01/18 15:45, 5F
→
01/18 15:46, , 6F
以拿來找disjoint set，雖然很不嚴謹，但寫的當下想法
01/18 15:46, 6F
→
01/18 15:46, , 7F
是這樣
01/18 15:46, 7F
→
01/18 15:51, , 8F
(c)如果union/find用上union by rank和path compressio
01/18 15:51, 8F
→
01/18 15:51, , 9F
應該可以比DFS消耗更少空間
01/18 15:51, 9F
推
01/18 18:09, , 10F
我的想法跟樓上一樣，如果用Union-and-find的空間會稍微
01/18 18:09, 10F
→
01/18 18:09, , 11F
少一些，就O(n)而已吧
01/18 18:09, 11F
→
01/18 18:16, , 12F
交大資演100分鐘要寫60題，我好多都沒有想得很完整...
01/18 18:16, 12F
推
01/18 18:28, , 13F
交大資演寫得完也是很猛QQ
01/18 18:28, 13F
推
01/18 18:33, , 14F
寫交大時間都不夠用QQ
01/18 18:33, 14F
推
01/18 18:42, , 15F
我想了想又覺得(c)的說法和空間複雜度可能還比較沒關？
01/18 18:42, 15F
→
01/18 18:44, , 16F
因為Graph很大，E和V都很多，所以如果用BFS/DFS要O(|V|+
01/18 18:44, 16F
→
01/18 18:44, , 17F
|E|),如果用Union-by-rank就只要O(log(N)),算是縮小了不
01/18 18:44, 17F
→
01/18 18:44, , 18F
少time complexity,所以可能是time complexity的問題
01/18 18:44, 18F
→
01/18 18:44, , 19F
晚點再研究看看
01/18 18:44, 19F
→
01/18 18:49, , 20F
當初我也有想到這個問題，但我是想說recursive會用到
01/18 18:49, 20F
→
01/18 18:49, , 21F
stack，如果recursive次數越少用的空間也越少，所以也
01/18 18:49, 21F
→
01/18 18:50, , 22F
可以算是跟space complexity有關？
01/18 18:50, 22F
推
01/18 18:56, , 23F
有相關，可是題目看不出來recursive次數少不少吧（？）
01/18 18:56, 23F
→
01/18 18:57, , 24F
因為他沒給圖，如果是一條長長的graph (像skew-tree)
01/18 18:57, 24F
→
01/18 18:57, , 25F
這樣space complexity就會滿低，不過這題純粹只有說一個
01/18 18:57, 25F
→
01/18 18:57, , 26F
大Graph
01/18 18:57, 26F
→
01/18 21:12, , 27F
也是沒錯拉...我這樣有點自己腦補了...
01/18 21:12, 27F
‣ 更多 PTTleader 的文章
文章代碼(AID): #1OVneeUu (Grad-ProbAsk)