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