→ 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

关键在step6每次可以排除n/4个points 所以下一次的递回才是T(3n/4)step4只是在n/2个数当中找中位数而已worst case就是中位数刚好也是中间值 所以只能排除掉n/4个xm应该是中间值 我误解题意了 抱歉

第三步找到的那些x有ceil(n/2) 个 第四步指的中点就是第三步所有点的中点

哦哦我以为这是couting跟radix混合XD 以为原文是用别的方法15题我再研究一下，感谢感谢 另外请问D大用n^2的array去排是怎么做？

我原本是直接想取n^2当base 但是其实复杂度超过也不能用XD