[理工] 資演 交大108 (10)(13)

[try66889 (貓貓只求黑琴ㄍㄟˋ婚 )]

想請問大家兩個大題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://www.ptt.cc/bbs/Grad-ProbAsk/M.1609933976.A.0EE.html
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 19:57:06
→ naive131: 10-2我挑最小1/3跟挑最大1/3都會使切割後最大的part大於
→ naive131: 2/3 所以我要挑中間1/3個
→ naive131: 10-3 每一輪我有2/3的機率要再做下一輪, 1+2/3+4/9+8/27
→ naive131: +...
→ naive131: 13-2他應該就是extract-max的時間複雜度吧？是的話那你B
→ naive131: C應該就會了
感謝n大~OWO!想再請問n大這邊extract-max是用fibonacci heap root改成存tree內的
最大值再像extract-min那樣extract-max 所以是O(log n)嗎? > <
→ mathtsai: 10-2 選中間1/3
了解~~感謝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
推 waes81224: 想請問 28的D和E選項為何會正確呢？
→ waes81224: 他不是取v1~vi取i次嗎？所以應該是O(i)=O(n)這樣理解
→ waes81224: 有那邊錯誤呢？
→ waes81224: 打錯 取vi+1~vn 取n-i次
因為選項寫line 5，所以應該只有算一次的而已~
※ 編輯: try66889 (114.32.191.76 臺灣), 01/06/2021 23:15:11
→ naive131: 是的，就是原本min-heap改成全部都是max-heap
了解惹~ 感謝n大OWO!
※ 編輯: try66889 (114.32.191.76 臺灣), 01/07/2021 14:27:49
※ 編輯: try66889 (114.32.191.76 臺灣), 01/07/2021 14:33:10
推 naive131: 原po抱歉，最近在重溫Fibonacci heap有去看一下wiki def
→ naive131: inition
→ naive131: 它的定義是a collection of heap-ordered trees，但是我
→ naive131: 有稍微查有沒有人用max-heap實作Fibonacci heap好像找不
→ naive131: 太到，不過我當初寫這題的時候就是想說可以這樣實作才選
→ naive131: 的，給你參考這樣子
了解~ 感謝n大~ 雖然比較少，不過我有看到有幾個人有用fibonacci heap作maximum
priority queue，所以應該是可行的 OWO! 感謝 > <
※ 編輯: try66889 (114.32.191.76 臺灣), 01/11/2021 16:29:39