[理工] 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