作者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/cn.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