基数排序时间

我正在学习本周的考试,我遇到了一个复习问题,要求......

0范围内的2千万个正整数。 。 。 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))?

0
额外 编辑
意见: 1
计算您的数字,它不是数千基数。
额外 作者 Daniel Fischer,
Myrias,如果你想吹嘘一点希腊语。或者一万,如果你想被理解。
额外 作者 Daniel Fischer,
似乎是这样(对于足够大的数据样本)。但实际关系可能不同,由于实现细节,缓存局部性......
额外 作者 Daniel Fischer,
那应该是theta(2(10000 + 20,000,000))?那个基数叫什么?
额外 作者 user1013032,
所以我可以说使用万基数大约是使用十进制基数的4倍?
额外 作者 user1013032,

1 答案

You're right that the runtime is O(d(n + k)). It might help to explicitly work out the relation between d and k. If you're dealing with numbers that go from 0 up to the number U, then the number of base-k digits in each number will be Θ(logk U) = Θ(log U/log k). This means that the runtime is more properly O(log U (n + k)/log k).

在您的情况下,k与n相比非常小,因此该运行时将具有for O(n log U/log k)。

Your claim that the runtimes would be Θ(8(10 + 20,000,000)) and Θ(3(1,000 + 20,000,000)) are a bit odd. Remember that Θ notation talks about long-term growth rates rather than individual values, so it's not meaningful to plug in values this way. However, your basic argument is correct. Going from base 10 to base 10000 is a 3-fold increase in the order of magnitude of the base, so you should expect the algorithm to be roughly three times faster with the larger base.

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

0
额外