[理工] 104台大電機丙 DS (11)(12)(16) jojoboy0115 PTT批踢踢實業坊

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

作者: jojoboy0115 (jojo) 2019-02-09 16:17:14

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要怎麼看?
以上再麻煩各位大大解說

作者: ekids1234 (∵:☆星痕╭☆) 2019-02-09 16:59:00

12題 Binomial Tree 合併就只有比大小然後合起來，O(1)E 對刪最小之後那顆下方會有其他 Binomial Tree 產生補充 Binomial Heap 合併 O(logn) Tree 是 O(1)

作者: eatagary (gary) 2019-02-09 17:04:00

12題他有說”two”兩顆合併一定是O（1），但是他沒說是兩顆的話，就是o(logn)

作者: ekids1234 (∵:☆星痕╭☆) 2019-02-09 17:06:00

11題 Link list 確認長度 O(n) : 從頭跑到尾

作者: eatagary (gary) 2019-02-09 17:06:00

O(logn) 拍謝手機大小寫不好打...

作者: GeniusPuddin (GeniusPudding) 2019-02-09 21:41:00

16E就因為裡面最大的clique可有e+1個點所以n/(e+1)

作者: magic83v (R7) 2019-02-10 03:34:00

請問G大這句是什麼意思 K4有6條邊可以有7個點？

繼續閱讀

[理工] 105中興資工離散Russ0116 [理工] 104台大電機丙 DS (2)(6)(7)jojoboy0115 [理工] 107台大電機丙資結第19題young60509 [理工] 104台大電機丙離散(1)(4)jojoboy0115 [理工]清大kaidi620 [理工] 107台大數學線代ouskit [理工] 107清大計科q5332159 [理工] 105交大計組AAQ8 [理工] 中正106計系beatssola [理工] 107 台聯電磁傳輸線pochen9