110 陽交大 資結

看板Grad-ProbAsk作者 (迷途の獅子)時間2年前 (2021/10/15 16:03), 2年前編輯推噓4(4推 0噓 20→)
留言24則, 3人參與, 2年前最新討論串1/1
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1634284982.A.CEA.html ※ 編輯: lienasd126 (115.43.138.74 臺灣), 10/15/2021 16:03:24
→
10/15 16:54, 2年前 , 1F
先回答Huffman code那題，如果是一般的binary Huffm
10/15 16:54, 1F
→
10/15 16:54, 2年前 , 2F
an tree, 不管有幾個character要encode都ok
10/15 16:54, 2F
→
10/15 16:56, 2年前 , 3F
但是這題是ternary Huffman tree, character數目要
10/15 16:56, 3F
→
10/15 16:56, 2年前 , 4F
是奇數才可以建好（想像每三個char合併成一個，char
10/15 16:56, 4F
→
10/15 16:56, 2年前 , 5F
數目會扣2，最後要剩下char數目必須要剩下一個）
10/15 16:56, 5F
→
10/15 16:57, 2年前 , 6F
可是這題給的char數目是偶數，這時候我們必須要inse
10/15 16:57, 6F
→
10/15 16:57, 2年前 , 7F
rt一個權重是0的placeholder node, 等到建好的時候
10/15 16:57, 7F
→
10/15 16:57, 2年前 , 8F
才remove, 這就是為什麼有些internal node的degree
10/15 16:57, 8F
→
10/15 16:57, 2年前 , 9F
不是3
10/15 16:57, 9F
嗯嗯，我再想想看
→
10/15 17:04, 2年前 , 10F
NP那題你的理由ok（畢竟題目沒講明problem是不是不
10/15 17:04, 10F
→
10/15 17:04, 2年前 , 11F
在P裡，NP包含P，所以在P裡的problem就是反例）
10/15 17:04, 11F
推
10/15 17:08, 2年前 , 12F
20. 如果空間不夠，就要分配一塊新的更大的mem, 再
10/15 17:08, 12F
→
10/15 17:08, 2年前 , 13F
把舊東西搬過去，所以可能要linear time
10/15 17:08, 13F
那這樣B的描述是正確的吧？！ 他答案沒給B,還有如果依照你那麼說應該時間複雜度是Bi g-O,不是Theta,他amortized下來是Theta(1) 謝謝Buster大 ※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:16:32
→
10/15 17:14, 2年前 , 14F
18. 這選項應該是錯的吧，光是merge就是O(nlgn)的時
10/15 17:14, 14F
→
10/15 17:14, 2年前 , 15F
間了 （高度lgn - lglgn，每個level O(n) ）
10/15 17:14, 15F
嗯嗯，對，我是想說題目的切法很像Selection, 所以搞不好時間複雜度很像XD ※ 編輯: lienasd126 (27.51.50.28 臺灣), 10/15/2021 17:18:27
→
10/15 17:24, 2年前 , 16F
20.B應該是錯在才多分配一單位吧== （m變成m+1，這
10/15 17:24, 16F
→
10/15 17:24, 2年前 , 17F
樣很快用不夠）
10/15 17:24, 17F
→
10/15 17:24, 2年前 , 18F
我看了一下vector的source code，至少也有+5
10/15 17:24, 18F
嗯嗯，好 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
→
10/15 17:55, 2年前 , 19F
對我的想法跟你說得差不多 所以應該BCD是不可能的
10/15 17:55, 19F
推
10/16 07:38, 2年前 , 20F
union 完美版需要 O(a(n)) a 為 inverse Ackermann fun
10/16 07:38, 20F
→
10/16 07:38, 2年前 , 21F
ction
10/16 07:38, 21F
推
10/16 23:43, 2年前 , 22F
請問huffman那題的答案是多少啊
10/16 23:43, 22F
BCD ※ 編輯: lienasd126 (27.53.186.34 臺灣), 10/17/2021 00:43:57
推
10/17 01:12, 2年前 , 23F
huffman那題看不懂為什麼B不行，NP那題的話，NP那
10/17 01:12, 23F
→
10/17 01:12, 2年前 , 24F
個選項反例就NPC(有Poly的解只是是用猜的猜出來的)
10/17 01:12, 24F
‣ 更多 lienasd126 的文章
文章代碼(AID): #1XQJMspg (Grad-ProbAsk)