作者try66889 (貓貓只求黑琴ㄍㄟˋ婚 )
看板Grad-ProbAsk
標題[理工] 資演 交大108 (10)(13)
時間Wed Jan 6 19:52:54 2021
想請問大家兩個大題QQ
10.(Solved)
https://i.imgur.com/31dFu8n.jpg
這題主要想請問2、3小題，完全沒有頭緒，不知道該從哪裡開始想QQ 只覺得和at most 2/3
有關，但想很久還是想不出什麼QQ
13.
https://i.imgur.com/Q6DHkmn.png
這題主要想請問1、2小題。
對題目的理解是若Vi到V_1-V_i-1所有邊的總和，是其餘V\{V1-V_i-1}到V_1-V_i-1中最大的
，那就是magic order。
不知道有沒有理解錯QQ
這題的第二小題主要想請問BC
B 是要改成O(log n)嗎?
C不知道為什麼對
謝謝大家QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.191.76 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1609933976.A.0EE.html
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 19:57:06
1F：→ naive131: 10-2我挑最小1/3跟挑最大1/3都會使切割後最大的part大於 01/06 20:23
2F：→ naive131: 2/3 所以我要挑中間1/3個 01/06 20:23
3F：→ naive131: 10-3 每一輪我有2/3的機率要再做下一輪, 1+2/3+4/9+8/27 01/06 20:23
4F：→ naive131: +... 01/06 20:23
5F：→ naive131: 13-2他應該就是extract-max的時間複雜度吧？是的話那你B 01/06 20:26
6F：→ naive131: C應該就會了 01/06 20:26
感謝n大~OWO!想再請問n大這邊extract-max是用fibonacci heap root改成存tree內的
最大值再像extract-min那樣extract-max 所以是O(log n)嗎? > <
7F：→ mathtsai: 10-2 選中間1/3 01/06 20:50
了解~~感謝m大 OWO!
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 21:21:22
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 21:21:46
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 21:24:01
8F：推 waes81224: 想請問 28的D和E選項為何會正確呢？ 01/06 22:43
9F：→ waes81224: 他不是取v1~vi取i次嗎？所以應該是O(i)=O(n)這樣理解 01/06 22:43
10F：→ waes81224: 有那邊錯誤呢？ 01/06 22:43
11F：→ waes81224: 打錯 取vi+1~vn 取n-i次 01/06 22:43
因為選項寫line 5，所以應該只有算一次的而已~
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 23:15:11
12F：→ naive131: 是的，就是原本min-heap改成全部都是max-heap 01/07 14:22
了解惹~ 感謝n大OWO!
※ 編輯: try66889 (114.32.191.76 臺灣), 01/07/2021 14:27:49
※ 編輯: try66889 (114.32.191.76 臺灣), 01/07/2021 14:33:10
13F：推 naive131: 原po抱歉，最近在重溫Fibonacci heap有去看一下wiki def 01/11 15:23
14F：→ naive131: inition 01/11 15:23
15F：→ naive131: 它的定義是a collection of heap-ordered trees，但是我 01/11 15:23
16F：→ naive131: 有稍微查有沒有人用max-heap實作Fibonacci heap好像找不 01/11 15:23
17F：→ naive131: 太到，不過我當初寫這題的時候就是想說可以這樣實作才選 01/11 15:23
18F：→ naive131: 的，給你參考這樣子 01/11 15:23
了解~ 感謝n大~ 雖然比較少，不過我有看到有幾個人有用fibonacci heap作maximum
priority queue，所以應該是可行的 OWO! 感謝 > <
※ 編輯: try66889 (114.32.191.76 臺灣), 01/11/2021 16:29:39