作者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/cn.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