我正在阅读算法介绍第 2 版，有一个问题说我们可以对 n 个整数进行排序，这些整数在线性时间内介于 0 和 n 3 -1 之间。我正在考虑 IBM 的基数排序方法。我从最低有效数字开始，根据最低有效数字分开数字，然后排序，然后根据下一个最低有效数字分开，依此类推。每次分离需要 O(n) 时间。但我有一个疑问，例如，如果其中一个数字由 n 位组成，那么算法需要 O(1*n+2*n+...+n*n)=O(n 2 ) 时间，对吗？我们能否保证数字由少于 n 个数字组成，或者任何人都可以为这个问题提供另一个提示？谢谢
问问题
2046 次
2 回答
3
基数排序的复杂性O(dn)与d数字中的位数一样。
d该算法仅在恒定时才以线性时间运行！在您的情况下d = 3log(n)，您的算法将在O(nlog(n)).
老实说，我不确定如何在线性时间内解决这个问题。有没有关于数字性质的任何其他信息我想知道是否缺少关于数字性质的任何其他信息......
于 2013-03-10T19:14:18.857 回答
2
假设一个词 RAM 模型，并且 n 适合 O(1) 个词，则有一个线性时间算法。
以 n 为底写下每个数字，并进行基数排序（使用稳定版本的计数排序作为基础数字排序）。
如果你想假设n无界，那么输入的大小实际上是n log n，在这种情况下基数排序再次起作用（在O（n log n）时间内），从技术上讲，它仍然是一个线性时间算法！（当然，我想这仍然假设算术是O（1）......）
于 2013-03-11T03:08:13.800 回答