看板 Grad-ProbAsk 關於我們 聯絡資訊
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1549787990.A.276.html
CorkiN: 21那個是說leftist heap,merge就是log(n) 02/10 16:45
Leaving: 21可以想成2n的array做build heap 所以是O(n) 02/10 17:58
Leaving: 哦看錯題目 沒事 02/10 17:59
yabi125: 22題有一樣的疑問 02/10 18:58
Leaving: 22不用merge 所有動作都在同一條array中完成的 02/10 19:04
Kanaheipapa: 25b 應該是都差不多O(V+E) 02/10 20:49
alen0303: 25C large資料反而更不適合DFS 需要擔心stack overflow 02/10 20:52
leviliang: BFS與DFS另外需要queue與stack排順序,只有union免 02/10 22:01
AAQ8: 想請問queue的話沒有overflow的問題嗎 02/10 23:31
leviliang: 一般來說實作上都會做到最大,也就是大小為|V|的陣列, 02/10 23:53
leviliang: 不會給他有機會overflow的。 02/10 23:54
AAQ8: 我懂了 感謝 02/11 10:23