[理工] 104 清大計算機科學第10題 bighb69738 PTT批踢踢實業坊

作者: bighb69738 (Vic) 2017-11-21 16:57:23

https://i.imgur.com/b4MrPcN.jpg
請問第10題能用下列這種解法嗎？
https://i.imgur.com/hR88xr0.jpg
麻煩大家幫我看一下感謝

作者: barry70490 (blacksea741) 2017-11-21 22:54:00

比較好奇是 mod√n 還是mod n

作者: sarsman (DeNT15T♠) 2017-11-21 23:56:00

已知S至少有√n個物品，感覺mod √n比較合理，做四次

作者: bighb69738 (Vic) 2017-11-22 00:20:00

https://i.imgur.com/gBm2wyR.jpg我原本也像s大這麼想但不確定行否

作者: barry70490 (blacksea741) 2017-11-22 00:44:00

http://i.imgur.com/NJT2QT8.jpg好像不是√n欸剛剛查了一下是nhttp://i.imgur.com/DODpbGq.jpg然後回應你的問題應該是只有這個方法因為其他不管怎麼做都沒有辦法O(|S|)

作者: JKLee (J.K.Lee) 2017-11-22 02:42:00

To big大,若S中的元素大小介於1~sqrt n之間,你寫在紙上的方法就無效

作者: bighb69738 (Vic) 2017-11-22 08:07:00

好的我了解了我時間不應該寫 n^1/2 因為用radix sort還是跳脫不出線性時間

作者: sarsman (DeNT15T♠) 2017-11-22 14:34:00

請問J大，為何會無效呢@@

作者: JKLee (J.K.Lee) 2017-11-22 21:59:00

對不起，我錯了。把big大寫在紙上的方法改成5個pass應該就可以了令n=4,key值範圍是1~16.使用LSD排序,共有√4=2個桶子.16以2進制表示為10000,共5位數.所以LSD排序須5個Pass.

作者: sarsman (DeNT15T♠) 2017-11-23 00:59:00

的確需要5次

繼續閱讀