作者lienasd126 (迷途の獅子)
看板Grad-ProbAsk
標題110 陽交大 資結
時間Fri Oct 15 16:03:00 2021
https://i.imgur.com/I2F2NEo.jpg
想請問26.D 如果是Union by rank(Height)不是O(logn)
https://i.imgur.com/q8XUmhQ.jpg
21.如果是（0，1，2）應該degree都是 3 ，怎麼有2的，有2的是不是不能選？
https://i.imgur.com/92fvbDh.jpg
20如果不計較size是不是 Linked list 比較好，如果是 direct access那應該選 array?
!
D. 如果是push_back 為什麼要花 Theta(n)
https://i.imgur.com/3K7ReEr.jpg
18 D 是不是把他看成 Selection Problem 時間也一樣？
https://i.imgur.com/una7Rgd.jpg
6.B floor (n/2) ^ floor(n/2) ，那個 floor要省略對嗎？
https://i.imgur.com/zDUnZJH.jpg
1. E P包含於NP，所以也可以solve in polynomial time?
請各位大神幫忙回答，感謝感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.138.74 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1634284982.A.CEA.html
※ 編輯: lienasd126 (115.43.138.74 臺灣), 10/15/2021 16:03:24
1F：→ BusterButter: 先回答Huffman code那題，如果是一般的binary Huffm10/15 16:54
2F：→ BusterButter: an tree, 不管有幾個character要encode都ok10/15 16:54
3F：→ BusterButter: 但是這題是ternary Huffman tree, character數目要10/15 16:56
4F：→ BusterButter: 是奇數才可以建好（想像每三個char合併成一個，char10/15 16:56
5F：→ BusterButter: 數目會扣2，最後要剩下char數目必須要剩下一個）10/15 16:56
6F：→ BusterButter: 可是這題給的char數目是偶數，這時候我們必須要inse10/15 16:57
7F：→ BusterButter: rt一個權重是0的placeholder node, 等到建好的時候10/15 16:57
8F：→ BusterButter: 才remove, 這就是為什麼有些internal node的degree10/15 16:57
9F：→ BusterButter: 不是310/15 16:57
嗯嗯，我再想想看
10F：→ BusterButter: NP那題你的理由ok（畢竟題目沒講明problem是不是不10/15 17:04
11F：→ BusterButter: 在P裡，NP包含P，所以在P裡的problem就是反例）10/15 17:04
12F：推 BusterButter: 20. 如果空間不夠，就要分配一塊新的更大的mem, 再10/15 17:08
13F：→ BusterButter: 把舊東西搬過去，所以可能要linear time10/15 17:08
那這樣B的描述是正確的吧？！ 他答案沒給B,還有如果依照你那麼說應該時間複雜度是Bi
g-O,不是Theta,他amortized下來是Theta(1)
謝謝Buster大
※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:16:32
14F：→ BusterButter: 18. 這選項應該是錯的吧，光是merge就是O(nlgn)的時10/15 17:14
15F：→ BusterButter: 間了 （高度lgn - lglgn，每個level O(n) ）10/15 17:14
嗯嗯，對，我是想說題目的切法很像Selection,
所以搞不好時間複雜度很像XD
※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:18:27
16F：→ BusterButter: 20.B應該是錯在才多分配一單位吧== （m變成m+1，這 10/15 17:24
17F：→ BusterButter: 樣很快用不夠） 10/15 17:24
18F：→ BusterButter: 我看了一下vector的source code，至少也有+5 10/15 17:24
嗯嗯，好
Huffman code 那一題是不是要看 placeholder node放的位置，如果不是放在最底層的就
是不可能，因為他是拿來湊的，是嗎？？
然後D選項是三位元樹不能有一個以上degree為2的點
※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:27:39
※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:29:15
※ 編輯: lienasd126 (115.43.138.74 臺灣), 10/15/2021 17:31:33
19F：→ BusterButter: 對我的想法跟你說得差不多 所以應該BCD是不可能的 10/15 17:55
20F：推 A4P8T6X9: union 完美版需要 O(a(n)) a 為 inverse Ackermann fun 10/16 07:38
21F：→ A4P8T6X9: ction 10/16 07:38
22F：推 joywilliamjo: 請問huffman那題的答案是多少啊 10/16 23:43
BCD
※ 編輯: lienasd126 (27.53.186.34 臺灣), 10/17/2021 00:43:57
23F：推 joywilliamjo: huffman那題看不懂為什麼B不行，NP那題的話，NP那 10/17 01:12
24F：→ joywilliamjo: 個選項反例就NPC(有Poly的解只是是用猜的猜出來的) 10/17 01:12
25F：推 jimmy1112111: 因為level2才少一個node，必須要在最底層才能少 10/27 00:46