我正在阅读 introduction to algorithms 2nd edition，有一道题说我们可以在线性时间内对 0 到 n3-1 之间的 n 个整数进行排序。我在考虑 IBM 的基数排序方法。我从最低有效数字开始，根据最低有效数字分隔数字，然后排序，然后根据下一个最低有效数字分隔等等。每次分离都需要 O(n) 时间。但是我有一个疑问，例如，如果其中一个数字由 n 位数字组成，那么该算法需要 O(1*n+2*n+...+n*n)=O(n2) 时间，对吗？我们能保证数字少于 n 位吗，或者任何人都可以为这个问题给出另一个提示吗？谢谢
最佳答案
基数排序的复杂度为 O(dn)，其中 d 为数字中的位数。
仅当d 为常量时，算法才以线性时间运行!在您的情况下 d = 3log(n) 并且您的算法将在 O(nlog(n)) 中运行。
老实说，我不确定如何在线性时间内解决这个问题。是否还有关于数字性质的任何其他信息我想知道是否还有关于数字性质的任何其他信息丢失......
关于algorithm - 线性时间排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15323740/