作者mistel (Mistel)
看板Grad-ProbAsk
标题Re: [理工] 104 清大 计算机科学
时间Thu Sep 26 23:58:56 2019
→ OppOops: 第三题T(n) = O(1)+O(1)+O(n)+O(n)+O(n)+T(3n/4) = O(n) 01/18 18:58
https://i.imgur.com/6wxVTXX.jpg
想问这题，O(3n/4)是怎麽来的？
感觉step4是关键但看不懂整句话...
: 推 OppOops: 确实O(d|S|)不会是O(|S|), 所以d要选择正确 01/18 21:42
: → OppOops: d想办法让它是常数... 如果radix有选好 01/18 21:43
: → OppOops: 提示: O( d * (|S| + radix) ), radix跟n有关 01/18 21:45
2.https://i.imgur.com/a1N9YVN.jpg
请问原文留言提到的用radix sort到底是怎麽找radix跟d的，我想了很久还是没有参透
另外我用counting sort的方法写了4回合的，请板上神人帮忙看一下对不对，感谢考题版赞
叹考题版
https://i.imgur.com/motFVwv.jpg
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.50.75 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1569513538.A.84F.html
1F：推 cossetannie: 关键在step6每次可以排除n/4个points 所以下一次的 09/27 00:45
2F：→ cossetannie: 递回才是T(3n/4) 09/27 00:45
3F：→ cossetannie: step4只是在n/2个数当中找中位数而已 09/27 00:47
4F：→ cossetannie: worst case就是中位数刚好也是中间值 所以只能排除 09/27 00:49
5F：→ cossetannie: 掉n/4个 09/27 00:49
6F：推 cossetannie: xm应该是中间值 我误解题意了 抱歉 09/27 01:32
7F：→ DLHZ: 第三步找到的那些x有ceil(n/2) 个 第四步指的中点就是第三步 09/27 08:44
8F：→ DLHZ: 所有点的中点 09/27 08:44
9F：→ DLHZ: radix sort要线性时间的话我只想到用n^2大的array下去排 09/27 11:05
10F：→ DLHZ: 你的写法看起来也没什麽问题 09/27 11:17
11F：→ DLHZ: 应该说你那个就是radix sort 09/27 11:23
12F：→ DLHZ: 这样看起来base不用取到n^2 用你的做法就可以 但是时间复杂 09/27 11:28
13F：→ DLHZ: 度应该是O(4(|S|+√n)) 09/27 11:28
14F：→ mistel: 哦哦我以为这是couting跟radix混合XD 以为原文是用别的方 09/27 18:09
15F：→ mistel: 法 09/27 18:09
16F：→ mistel: 15题我再研究一下，感谢感谢 另外请问D大用n^2的array去 09/27 18:10
17F：→ mistel: 排是怎麽做？ 09/27 18:10
18F：→ DLHZ: 我原本是直接想取n^2当base 但是其实复杂度超过也不能用XD 09/27 18:20