Re: [理工] 104 清大 計算機科學

看板Grad-ProbAsk作者 (Mistel)時間6年前 (2019/09/26 23:58), 編輯推噓2(2推 0噓 16→)
留言18則, 3人參與, 6年前最新討論串2/2 (看更多)
→ 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1569513538.A.84F.html
推
09/27 00:45, 6年前 , 1F
關鍵在step6每次可以排除n/4個points 所以下一次的
09/27 00:45, 1F
→
09/27 00:45, 6年前 , 2F
遞迴才是T(3n/4)
09/27 00:45, 2F
→
09/27 00:47, 6年前 , 3F
step4只是在n/2個數當中找中位數而已
09/27 00:47, 3F
→
09/27 00:49, 6年前 , 4F
worst case就是中位數剛好也是中間值 所以只能排除
09/27 00:49, 4F
→
09/27 00:49, 6年前 , 5F
掉n/4個
09/27 00:49, 5F
推
09/27 01:32, 6年前 , 6F
xm應該是中間值 我誤解題意了 抱歉
09/27 01:32, 6F
→
09/27 08:44, 6年前 , 7F
第三步找到的那些x有ceil(n/2) 個 第四步指的中點就是第三步
09/27 08:44, 7F
→
09/27 08:44, 6年前 , 8F
所有點的中點
09/27 08:44, 8F
→
09/27 11:05, 6年前 , 9F
radix sort要線性時間的話我只想到用n^2大的array下去排
09/27 11:05, 9F
→
09/27 11:17, 6年前 , 10F
你的寫法看起來也沒什麼問題
09/27 11:17, 10F
→
09/27 11:23, 6年前 , 11F
應該說你那個就是radix sort
09/27 11:23, 11F
→
09/27 11:28, 6年前 , 12F
這樣看起來base不用取到n^2 用你的做法就可以 但是時間複雜
09/27 11:28, 12F
→
09/27 11:28, 6年前 , 13F
度應該是O(4(|S|+√n))
09/27 11:28, 13F
→
09/27 18:09, 6年前 , 14F
哦哦我以為這是couting跟radix混合XD 以為原文是用別的方
09/27 18:09, 14F
→
09/27 18:09, 6年前 , 15F
法
09/27 18:09, 15F
→
09/27 18:10, 6年前 , 16F
15題我再研究一下，感謝感謝 另外請問D大用n^2的array去
09/27 18:10, 16F
→
09/27 18:10, 6年前 , 17F
排是怎麼做？
09/27 18:10, 17F
→
09/27 18:20, 6年前 , 18F
我原本是直接想取n^2當base 但是其實複雜度超過也不能用XD
09/27 18:20, 18F
‣ 更多 mistel 的文章
文章代碼(AID): #1TZE12XF (Grad-ProbAsk)
‣ 更多 mistel 的文章
文章代碼(AID): #1TZE12XF (Grad-ProbAsk)