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