0

如果我们有一些m > 0 并且需要提供一种算法来在时间 O(mn)内对 0 到n^m -1 范围内的n 个整数进行排序。我的建议是： 

Radix-Sort(A,t)  // t is the digit length
for i=0 to t
    do Insertion-Sort A on digit i

我的论点是，上述内容将以 O(mn) 运行，因为对于每个数字 t - 插入排序将花费 O(n) 时间，因为每次运行的范围很小。

这是正确的建议吗？上面的空间要求应该是多少？

谢谢。

4

2 回答 2

1

在对小范围的离散数字进行排序时，最好使用计数排序，因此它可以保证搜索在数据大小及其范围方面的线性（插入排序是一种具有O(n^2)最坏情况复杂度的比较排序，但如果数据以相反的方向排序，小范围可能不会帮助您进行插入排序，因为每个元素都会被移动）。

使用计数排序时的空间复杂度为O(n+k)，其中 n 是数组的大小，k 是数据的范围。您可以使用相同的数组对结果进行排序和返回，因为您正在对原始数据进行排序。

于 2011-11-05T14:37:53.147 回答
0

空间要求为 O(m + n)，因为您需要原始数字和 m 个存储桶来放置 n 个项目。运行时间是 O(mn)，可以是 >> n，这是基数排序的问题。在所有情况下它的 O(mn) 但问题是如果 m > n 你得到的东西大于 O(n^2)。根据它的写入方式，在最坏的情况下，内存也可能是 O(mn)，因为您创建了 n 个数字集的 m 个副本以进行排序。

于 2011-11-05T02:19:35.053 回答