作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 105交大資演
時間Sun Feb 10 16:39:48 2019
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)錯在哪裡
麻煩各位
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.194.82
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549787990.A.276.html
1F：推 CorkiN: 21那個是說leftist heap，merge就是log(n) 02/10 16:45
2F：→ Leaving: 21可以想成2n的array做build heap 所以是O(n) 02/10 17:58
3F：→ Leaving: 哦看錯題目 沒事 02/10 17:59
4F：推 yabi125: 22題有一樣的疑問 02/10 18:58
5F：→ Leaving: 22不用merge 所有動作都在同一條array中完成的 02/10 19:04
6F：推 Kanaheipapa: 25b 應該是都差不多O(V+E) 02/10 20:49
7F：推 alen0303: 25C large資料反而更不適合DFS 需要擔心stack overflow 02/10 20:52
8F：推 leviliang: BFS與DFS另外需要queue與stack排順序，只有union免 02/10 22:01
9F：→ AAQ8: 想請問queue的話沒有overflow的問題嗎 02/10 23:31
10F：→ leviliang: 一般來說實作上都會做到最大，也就是大小為|V|的陣列， 02/10 23:53
11F：→ leviliang: 不會給他有機會overflow的。 02/10 23:54
12F：→ AAQ8: 我懂了 感謝 02/11 10:23