推 cossetannie: 關鍵在step6每次可以排除n/4個points 所以下一次的 09/27 00:45
→ cossetannie: 遞迴才是T(3n/4) 09/27 00:45
→ cossetannie: step4只是在n/2個數當中找中位數而已 09/27 00:47
→ cossetannie: worst case就是中位數剛好也是中間值 所以只能排除 09/27 00:49
→ cossetannie: 掉n/4個 09/27 00:49
推 cossetannie: xm應該是中間值 我誤解題意了 抱歉 09/27 01:32
→ DLHZ: 第三步找到的那些x有ceil(n/2) 個 第四步指的中點就是第三步 09/27 08:44
→ DLHZ: 所有點的中點 09/27 08:44
→ DLHZ: radix sort要線性時間的話我只想到用n^2大的array下去排 09/27 11:05
→ DLHZ: 你的寫法看起來也沒什麼問題 09/27 11:17
→ DLHZ: 應該說你那個就是radix sort 09/27 11:23
→ DLHZ: 這樣看起來base不用取到n^2 用你的做法就可以 但是時間複雜 09/27 11:28
→ DLHZ: 度應該是O(4(|S|+√n)) 09/27 11:28
→ mistel: 哦哦我以為這是couting跟radix混合XD 以為原文是用別的方 09/27 18:09
→ mistel: 法 09/27 18:09
→ mistel: 15題我再研究一下，感謝感謝 另外請問D大用n^2的array去 09/27 18:10
→ mistel: 排是怎麼做？ 09/27 18:10
→ DLHZ: 我原本是直接想取n^2當base 但是其實複雜度超過也不能用XD 09/27 18:20