作者jojoboy0115 (その血の运命~Jo~Jo~)
看板Grad-ProbAsk
标题[理工] 104台大电机丙 DS (11)(12)(16)
时间Sat Feb 9 16:17:14 2019
https://i.imgur.com/lHfnlzN.jpg
答案 BCDE
请问11题的E为什麽错?
计算Size是O(n)，跑到_last吗?
empty 是只要O(1)吗?
https://i.imgur.com/fcGAQ5l.jpg
答案ACE
请问12题的D是错在只要O(1)吗?
E是因为删除最小的node 也会分裂成其他Binomial Tree吗?
https://i.imgur.com/Mu93bW9.jpg
答案DE
请问16题的E要怎麽看?
以上再麻烦各位大大解说
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.246.30.11
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549700237.A.AA6.html
1F：推 ekids1234: 12题 Binomial Tree 合并就只有比大小然後合起来，O(1) 02/09 16:59
2F：→ ekids1234: E 对 删最小之後那颗下方会有其他 Binomial Tree 产生 02/09 17:01
3F：→ ekids1234: 补充 Binomial Heap 合并 O(logn) Tree 是 O(1) 02/09 17:02
4F：→ eatagary: 12题 他有说”two”两颗合并一定是O（1），但是他没说是 02/09 17:04
5F：→ eatagary: 两颗的话，就是o(logn) 02/09 17:04
6F：推 ekids1234: 11题 Link list 确认长度 O(n) : 从头跑到尾 02/09 17:06
7F：→ eatagary: O(logn) 拍谢 手机大小写不好打... 02/09 17:06
8F：→ ekids1234: 确认 empty O(1) : 只要看 head 是否 = Null 即可 02/09 17:06
9F：→ GeniusPuddin: 16E就因为里面最大的clique可有e+1个点所以n/(e+1) 02/09 21:41
10F：→ magic83v: 请问G大这句是什麽意思 K4有6条边 可以有7个点？ 02/10 03:34
11F：推 jimmylin1024: 12 题 D是对的 因为O(1)照定义的话就是O(logn )（无 12/12 09:52
12F：→ jimmylin1024: 法说它的upper bound 不是logn 的意思） 12/12 09:52