基数排序时间

我学习了一个测试，这个星期我已经和我对面，询问审查问题就来了......基数排序时间

二十万元范围为0的正整数。。。 99,999,999按LSD基数排序。比较使用基数0的性能。。。 9999和基数0。。。 9.显示你的工作。我知道基数排序的时间是theta（d（k + n））;其中d =数字位数k =基数大小，n =记录数。

我明白十进制基数是theta（8（10 + 20,000,000）），对吗？

千位基数是多少？ THETA（3（1000 + 20000000））？

来源

2011-11-17 user1013032

计算你的数字，它不是千位基数。 –

那么它应该是theta（2（10000 + 20,000,000））？那个基数会被称为什么？ – user1013032

Myrias，如果你想吹嘘一点希腊。如果你想要被理解的话，还是一万个。 –

你说得对，运行时间是O（d（n + k））。这可能有助于明确d和k之间的关系。如果您处理的数字从0到数字U，则每个数字中的基数k数字将为Θ（日志_k U）= Θ（log U/log k）。这意味着运行时更适合O（log U（n + k）/ log k）。

在你的情况下，k与n相比非常小，所以这个运行时会有O（n log U/log k）。

您声称运行时间为Θ（8（10 + 20,000,000））和Θ（3（1,000 + 20,000,000））有点奇怪。请记住Θ表示法谈论长期增长率而不是个别价值，所以用这种方式插入价值没有意义。但是，你的基本论点是正确的。从基数10到基数10000是基数的数量级的3倍增加，所以你应该期望算法在基数较大的情况下快三倍。

也就是说，还有很多其他因素可能会在实践中搞砸这个时机。引用的局部性在执行大量数组操作的算法的运行时间中起着巨大的作用，并且随着您增加桶的数量，您的局部性会逐渐变差。这可能实际上最终使大基排序比小基排序慢，因为即使轮数较少，由于缓存效应每轮都会花费更长的时间。没有尝试过，我敢打赌，这很有可能是在实践中会发生的。

来源

2015-08-26 19:44:35 templatetypedef

基数排序时间

回答

相关问题