→ 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