yra*_*lik 6 sorting algorithm big-o radix-sort
我正在阅读算法第2版的介绍,并且有一个问题说我们可以排序n个整数,它们在线性时间内介于0和n 3 -1 之间.我正在考虑IBM的基数排序方法.我从最低有效数字开始,相对于最低有效数字分开数字,然后排序,然后相对于下一个最低有效数字分开,依此类推.每次分离需要O(n)次.但我有一个疑问,例如,如果其中一个数字由n个数字组成,那么算法需要O(1*n + 2*n + ... + n*n)= O(n 2)时间,对吗？我们能否确保数字少于n位数,或者是否有人可以提出另一个问题提示？谢谢
Mar*_*ace 3
基数排序复杂度与数字中的位数有关O(dn)。d
O(dn)
d
仅当 为常数时，该算法才以线性时间运行d！在您的情况下d = 3log(n)，您的算法将在O(nlog(n)).
d = 3log(n)
O(nlog(n))
老实说，我不确定如何在线性时间内解决这个问题。是否还有关于数字性质的任何其他信息我想知道是否还缺少有关数字性质的任何其他信息......
归档时间：
13 年，5 月 前
查看次数：
1905 次
最近记录：