[理工] 105交大資演 AAQ8 PTT批踢踢實業坊

[理工] 105交大資演

作者: AAQ8 (不要就是要) 2019-02-10 16:39:48

https://i.imgur.com/pwob9ds.jpg
https://i.imgur.com/a4sbWMr.jpg
https://i.imgur.com/uM7pTnM.jpg
21的(C)選項
我知道heap的插入和刪除都是logn
但merging two min-heap是什麼意思
22的(C)選項
Qsort不是還有花O(1)的時間merge嗎
為什麼可以說不用花時間作merge
25想問(B)(C)錯在哪裡
麻煩各位
感謝

作者: CorkiN (柯基) 2019-02-10 16:45:00

21那個是說leftist heap，merge就是log(n)

作者: Leaving 2019-02-10 17:58:00

21可以想成2n的array做build heap 所以是O(n)哦看錯題目沒事

作者: yabi125 (春捲) 2019-02-10 18:58:00

22題有一樣的疑問

作者: Leaving 2019-02-10 19:04:00

22不用merge 所有動作都在同一條array中完成的

作者: Kanaheipapa (趴趴) 2019-02-10 20:49:00

25b 應該是都差不多O(V+E)

作者: alen0303 (艾倫零參智商負三) 2019-02-10 20:52:00

25C large資料反而更不適合DFS 需要擔心stack overflow

作者: leviliang (levi) 2019-02-10 22:01:00

BFS與DFS另外需要queue與stack排順序，只有union免

作者: AAQ8 (不要就是要) 2019-02-10 23:31:00

想請問queue的話沒有overflow的問題嗎

作者: leviliang (levi) 2019-02-10 23:53:00

一般來說實作上都會做到最大，也就是大小為|V|的陣列，不會給他有機會overflow的。

作者: AAQ8 (不要就是要) 2019-02-11 10:23:00

我懂了感謝

繼續閱讀

[理工] 105 電機丙數haniwang [離散] 命題lionccc [理工] 離散 pseudo graph表示ncdonalds123 [理工] 104台大資工計系TonyXIAO [理工] 計系問題求救beatssola 107清大計組kaidi620 [理工] 107交大數學kaidi620 [理工] 107台科數學Marcolod [理工] 台聯大106 電子Rexasto [理工] 中興程式題rustw2010