[理工] 106 成大電通資結 magic83v PTT批踢踢實業坊

作者: magic83v (R7) 2019-02-21 19:57:08

想討論一下選擇題答案
https://i.imgur.com/t1zNRkG.jpg
1.
2. D
3. BC
4. D
第一題剩C能選但是沒看過bfs的back edge(?
二的a 最差是O(n) 嗎？
感謝各位

作者: tataTangQQ (TaTa) 2019-02-21 21:01:00

Rule by weight應該就是O(lgn)吧

作者: CorkiN (柯基) 2019-02-21 21:46:00

同意樓上第一題，依tree的定義，就是acyclic了，應該不會有back edge，我不會選它

作者: magic83v (R7) 2019-02-21 22:22:00

有沒有n個點都不同set 的情況第一次find要找n個set?

作者: sooge (老衲) 2019-02-21 22:44:00

第一題A不對嗎？

作者: alily86 (lily) 2019-02-22 00:07:00

A對吧

作者: magic83v (R7) 2019-02-22 00:41:00

最快的怪怪的(? 那換成dfs 也對嗎

作者: sooge (老衲) 2019-02-22 01:20:00

BFS和DFS最快都是V+E 想說怎麼沒人要選

作者: magic83v (R7) 2019-02-22 13:30:00

所以1.A可以 2.A也對嗎q

作者: alily86 (lily) 2019-02-22 14:08:00

第四題錯了吧 max heapify最快是nlogn

作者: magic83v (R7) 2019-02-22 15:10:00

4你覺得哪個對

作者: sooge (老衲) 2019-02-22 18:43:00

2我不知道不過4是D沒錯選項說最快最快就是不用調把node檢查一遍而已所以才會是n問一般的時間複雜度才會是nlgn

作者: magic83v (R7) 2019-02-22 19:39:00

ok 感謝各位

繼續閱讀