[理工] 105交大資演

看板Grad-ProbAsk作者時間6年前 (2019/02/10 16:39), 編輯推噓5(5推 0噓 7→)
留言12則, 7人參與, 6年前最新討論串8/10 (看更多)
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
推
02/10 16:45, 6年前 , 1F
21那個是說leftist heap，merge就是log(n)
02/10 16:45, 1F
→
02/10 17:58, 6年前 , 2F
21可以想成2n的array做build heap 所以是O(n)
02/10 17:58, 2F
→
02/10 17:59, 6年前 , 3F
哦看錯題目 沒事
02/10 17:59, 3F
推
02/10 18:58, 6年前 , 4F
22題有一樣的疑問
02/10 18:58, 4F
→
02/10 19:04, 6年前 , 5F
22不用merge 所有動作都在同一條array中完成的
02/10 19:04, 5F
推
02/10 20:49, 6年前 , 6F
25b 應該是都差不多O(V+E)
02/10 20:49, 6F
推
02/10 20:52, 6年前 , 7F
25C large資料反而更不適合DFS 需要擔心stack overflow
02/10 20:52, 7F
推
02/10 22:01, 6年前 , 8F
BFS與DFS另外需要queue與stack排順序，只有union免
02/10 22:01, 8F
→
02/10 23:31, 6年前 , 9F
想請問queue的話沒有overflow的問題嗎
02/10 23:31, 9F
→
02/10 23:53, 6年前 , 10F
一般來說實作上都會做到最大，也就是大小為|V|的陣列，
02/10 23:53, 10F
→
02/10 23:54, 6年前 , 11F
不會給他有機會overflow的。
02/10 23:54, 11F
→
02/11 10:23, 6年前 , 12F
我懂了 感謝
02/11 10:23, 12F
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SN-DM9s (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 8 之 10 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 AAQ8 的文章
文章代碼(AID): #1SN-DM9s (Grad-ProbAsk)