[理工] 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次

继续阅读