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

看板Grad-ProbAsk作者 (その血の運命~Jo~Jo~)時間6年前 (2019/02/09 16:17), 編輯推噓2(2推 0噓 8→)
留言10則, 4人參與, 6年前最新討論串1/1
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
推
02/09 16:59, 6年前 , 1F
12題 Binomial Tree 合併就只有比大小然後合起來，O(1)
02/09 16:59, 1F
→
02/09 17:01, 6年前 , 2F
E 對 刪最小之後那顆下方會有其他 Binomial Tree 產生
02/09 17:01, 2F
→
02/09 17:02, 6年前 , 3F
補充 Binomial Heap 合併 O(logn) Tree 是 O(1)
02/09 17:02, 3F
→
02/09 17:04, 6年前 , 4F
12題 他有說”two”兩顆合併一定是O（1），但是他沒說是
02/09 17:04, 4F
→
02/09 17:04, 6年前 , 5F
兩顆的話，就是o(logn)
02/09 17:04, 5F
推
02/09 17:06, 6年前 , 6F
11題 Link list 確認長度 O(n) : 從頭跑到尾
02/09 17:06, 6F
→
02/09 17:06, 6年前 , 7F
O(logn) 拍謝 手機大小寫不好打...
02/09 17:06, 7F
→
02/09 17:06, 6年前 , 8F
確認 empty O(1) : 只要看 head 是否 = Null 即可
02/09 17:06, 8F
→
02/09 21:41, 6年前 , 9F
16E就因為裡面最大的clique可有e+1個點所以n/(e+1)
02/09 21:41, 9F
→
02/10 03:34, 6年前 , 10F
請問G大這句是什麼意思 K4有6條邊 可以有7個點？
02/10 03:34, 10F
‣ 更多 jojoboy0115 的文章
文章代碼(AID): #1SNeoDgc (Grad-ProbAsk)