[理工] 104 清大 計算機科學 第10題

看板Grad-ProbAsk作者 (Vic)時間8年前 (2017/11/21 16:57), 編輯推噓6(6推 0噓 13→)
留言19則, 4人參與, 8年前最新討論串1/1
https://i.imgur.com/b4MrPcN.jpg
請問 第10題 能用下列這種解法嗎？ https://i.imgur.com/hR88xr0.jpg
麻煩大家幫我看一下 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.217.195.41 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511254646.A.011.html
推
11/21 22:54, 8年前 , 1F
比較好奇是 mod√n 還是mod n
11/21 22:54, 1F
推
11/21 23:56, 8年前 , 2F
已知S至少有√n個物品，感覺mod √n比較合理，做四次
11/21 23:56, 2F
→
11/22 00:20, 8年前 , 3F
11/22 00:20, 3F
→
11/22 00:21, 8年前 , 4F
我原本也像s大這麼想 但不確定行否
11/22 00:21, 4F
推
11/22 00:44, 8年前 , 5F
11/22 00:44, 5F
→
11/22 00:44, 8年前 , 6F
好像不是√n欸 剛剛查了一下是n
11/22 00:44, 6F
→
11/22 00:46, 8年前 , 7F
11/22 00:46, 7F
→
11/22 00:46, 8年前 , 8F
然後回應你的問題 應該是只有這個方法因為其他不管怎
11/22 00:46, 8F
→
11/22 00:46, 8年前 , 9F
麼做都沒有辦法O(|S|)
11/22 00:46, 9F
推
11/22 02:42, 8年前 , 10F
To big大,若S中的元素大小介於1~sqrt n之間,你寫在紙上的
11/22 02:42, 10F
→
11/22 02:42, 8年前 , 11F
方法就無效
11/22 02:42, 11F
→
11/22 08:07, 8年前 , 12F
好的我了解了 我時間不應該寫 n^1/2 因為用radix sort
11/22 08:07, 12F
→
11/22 08:07, 8年前 , 13F
還是跳脫不出 線性時間
11/22 08:07, 13F
推
11/22 14:34, 8年前 , 14F
請問J大，為何會無效呢@@
11/22 14:34, 14F
推
11/22 21:59, 8年前 , 15F
對不起，我錯了。把big大寫在紙上的方法改成5個pass應該就
11/22 21:59, 15F
→
11/22 21:59, 8年前 , 16F
可以了
11/22 21:59, 16F
→
11/23 00:23, 8年前 , 17F
令n=4,key值範圍是1~16.使用LSD排序,共有√4=2個桶子.
11/23 00:23, 17F
→
11/23 00:23, 8年前 , 18F
16以2進制表示為10000,共5位數.所以LSD排序須5個Pass.
11/23 00:23, 18F
→
11/23 00:59, 8年前 , 19F
的確需要5次
11/23 00:59, 19F
‣ 更多 bighb69738 的文章
文章代碼(AID): #1Q4-fs0H (Grad-ProbAsk)