[理工] 104台大電機丙 DS (11)(12)(16)

[jojoboy0115 (その血の運命~Jo~Jo~)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1549700237.A.AA6.html
推 ekids1234: 12題 Binomial Tree 合併就只有比大小然後合起來，O(1)
→ ekids1234: E 對  刪最小之後那顆下方會有其他 Binomial Tree 產生
→ ekids1234: 補充 Binomial Heap 合併 O(logn) Tree 是 O(1)
→ eatagary: 12題 他有說”two”兩顆合併一定是O（1），但是他沒說是
→ eatagary: 兩顆的話，就是o(logn)
推 ekids1234: 11題 Link list 確認長度 O(n) : 從頭跑到尾
→ eatagary: O(logn) 拍謝 手機大小寫不好打...
→ ekids1234: 確認 empty O(1) : 只要看 head 是否 = Null 即可
→ GeniusPuddin: 16E就因為裡面最大的clique可有e+1個點所以n/(e+1)
→ magic83v: 請問G大這句是什麼意思 K4有6條邊 可以有7個點？
推 jimmylin1024: 12 題 D是對的 因為O(1)照定義的話就是O(logn )（無
→ jimmylin1024: 法說它的upper bound 不是logn 的意思）