线性时间排序

Question

我正在阅读算法导论第二版，其中有一个问题说我们可以在线性时间内对介于0和n³-1之间的n个整数进行排序。我考虑使用IBM的基数排序方法。我从最低有效位开始，根据最低有效位将数字分开，然后排序，接着按照次低有效位分开并排序，以此类推。每个分离需要O(n)时间。但我有一个疑问，例如，如果其中一个数字包含n位数字，则该算法需要O(1*n+2*n+...+n*n)=O(n²)时间，对吗？我们可以保证数字少于n位数吗？还是有人能给出这个问题的另一个提示吗？谢谢

- yrazlik

---

每个数字都介于0和n³-1之间，因此在n进制下最多有3位数。 - Ivaylo Strandjev

谢谢，凭借这些信息，我的解决方案可以正常工作了？ - yrazlik

@IvayloStrandjev：在我看来，这基本上已经是一个答案了。你应该（重新）发布它，不过你可以给一些详细信息，介绍如何在仅三步内完成排序。 - nneonneo

相关：线性时间排序？ - jfs

Answer 1

基数排序的复杂度是O(dn)，其中d是数字中位数的数量。

当d为常数时，该算法仅以线性时间运行！在您的情况下，d = 3log(n)，因此您的算法将以O(nlog(n))运行。

老实说，我不确定如何以线性时间解决这个问题。是否有关于数字性质的其他信息？我想知道是否缺少任何其他信息...

- Marsellus Wallace

---

谢谢你的回答，实际上我已经找到了答案。我们将数字视为基数为n的两位数，然后对这些两位数进行排序。总时间复杂度为O(n)。 - yrazlik

如果您将一个数字以两位“键”拆分，最终会得到“d = 3log(n) / 2”，您是否有该算法详细分析的链接？谢谢。 - Marsellus Wallace

@bigO: 1. n**3-1 在基数为 n 的情况下需要 3 位数字。2. 你不能期望对于任意大的 n，在基数为 n 的情况下操作一个数字是 O(1)（常数时间）。 - jfs

@Gevorg：你还没有理解我想说的。如果你认为数字的位数很_重要_，那么你应该在运行时分析中始终如一地考虑它：即在计算输入大小时也要考虑。我声称，为了保持一致（和正确），您必须将输入大小视为Theta(dn)（或Theta(n log n)）。如果是这样，根据定义，基数排序_是_线性的。如果您将输入大小视为Theta(n)，则隐含地假定了WORD RAM模型（整数适合一个字），在这种情况下，您的d基本上是常数！ - Knoothe

（注意：我正在谈论当前的问题，其中每个整数都在范围n^3-1内，通过以基数n写入，数字的位数是恒定的） - Knoothe

Answer 2

假设采用字RAM模型，并且n适合于O(1)个字，这时有一种线性时间算法。

将每个数字写成n进制，并使用基数排序（底层位排序采用稳定的计数排序）。

如果要假设n无限大，则输入的大小实际上是n log n。这种情况下，基数排序仍然适用（在O(n log n)的时间内），而从技术角度来说，它仍然是一种线性时间算法！（当然，我想这还是假设算术时间复杂度为O(1)...）

- Knoothe

---

“linearithmic” 实际上是 “线性的” 吗？ - Marsellus Wallace

自从我们开始交流以来，我想跟进一下！ :) 我不确定你是如何得出 O(nlog(n)) 的，但如果你认为这是一个线性解决方案，那么使用良好的快速排序、归并排序或其他算法实现，问题将变得非常简单... - Marsellus Wallace

@Gevorg：不，比较整数的时间复杂度是O(log n)，而快速排序等算法的时间复杂度是Theta(n (log n)^2)。底层计算模型非常重要。大多数算法教材使用WORD RAM模型（实际上，大多数人在不加思考的情况下使用它，因为它最接近真实的计算机）。在这种情况下（即在WORD RAM模型中），输入大小为Theta(n)，基数排序的时间复杂度为O(n)，而快速排序等的时间复杂度为O(n log n)。 - Knoothe

（再次强调）我所说的是当前问题，其中整数小于n^3。 - Knoothe