可能是重复问题:
如何在线性时间内排序？
假设我们有一个包含n个元素的序列S，每个元素都是范围在[0，n^2-1]之间的整数。 我们能否在O(n)时间内对其进行排序？
请不要介意我问了太多的面试问题。我只是想学习。
7个回答
10
序号。
当唯一的前提条件是在0-N²范围内的整数时。
- 计数排序不起作用，因为扫描，无论是对于不同输入的位模式还是对于重复输入的桶，都需要O(N²)的时间完成。
- 范围会使得基数排序的关键字长度取决于N，因此基数排序不能在O(N)的时间内工作。
任何涉及“当N很小时”的陈述都会使任何基于O的论证无效。
- Captain Giraffe
0
如果
n 足够小，您可以使用直方图。从输入序列构建直方图，然后从该直方图构造输出序列。伪代码：
H = histogram(input_sequence);
while (not H.empty):
E = H.smallest_value_element()
//E.value - value of element, E.count - count in input sequence
H.remove(E)
repeat E.count times: output_sequence.append(E.value)
- Adam Trhon
0
是的，如果我们有一个类似哈希函数的东西，可以在O(1)时间内计算任何整数在排序数组中的位置。然而，设计这样的哈希函数在我看来是有问题的 - 我想不出任何详细的想法来解决它。
- sharptooth
3
你的哈希函数如何在不知道0是否在S中的情况下决定值1的位置？ - dfan
@dfan：不知道，那只是一个“这就是我们需要的”的回答。 - sharptooth
对我来说似乎是不可能的，因为一个整数在排序数组中的位置取决于 S 中其他元素的值。 - dfan
0
编程珠玑涵盖了这个问题的变化。如果S很大并且可以假设没有重复项，则最快的方法是分配长度为n ^ 2的位向量，并使用它来标记范围内每个数字的存在或不存在。
- RossFabricant
1
分配一个长度为n^2的位向量，这使得对OP的回答变得明确，是否定的。 - Captain Giraffe
-2
如果有n^2-1个比特的内存可用，只需扫描序列，将由序列值索引的每个位设置为1。这是关于序列大小的O(n)操作。随后，测试存在性就成为了一个O(1)操作。
当然，如果你想读取排序后的序列，它的时间复杂度是O(n^2)，因为你需要扫描整个n^2-1个比特的集合来查找1s。
当然，如果你想读取排序后的序列，它的时间复杂度是O(n^2)，因为你需要扫描整个n^2-1个比特的集合来查找1s。
- joel.neely
6
当然，如果你想读出排序后的序列，这难道不等同于说：如果你知道一个O(1)问题的算法，但是如果你想找到答案，结果可能会有所不同。 - Captain Giraffe
10实际上，生成已排序序列似乎是排序序列的相当大的一部分。如果被允许花费O(n^2)的时间来读取已排序的序列，那么我可以在零时间内对任何序列进行排序。 - dfan
你能再解释一下这个答案吗？我认为它没有清楚地说明如何得到一个排序好的元素序列。 - Sammy Larbi
引言中的“如果有n^2-1个比特的内存可用”是多余的。问题只涉及时间限制，因此有任意数量的可用内存。如果你是理论计算机科学家的话。 - Philip
@Philip: 每个内存限制都可以被平凡地视为时间限制，因为你无法在少于O（N）的时间内读取或写入N个内存。 - Paŭlo Ebermann
@Paŭlo：是的，但我可以在固定的时间内写入固定数量的存储器，而且与 N 无关。例如，如果我将归并排序更改为首先计算前1000000个质数，然后像预期的那样继续进行归并排序，则这不会改变归并排序的渐近运行时间 O(n*log n)。如果没有存储器约束，则存储器是无限的。 - Philip
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接