在 O(n) 中将 n 个数字从 0 排序到 n^m 的算法？其中 m 是常数

Question

所以我在以下地方遇到了这个问题:

我们必须对 0 到 n^3 之间的 n 个数字进行排序，时间复杂度的答案是 O(n)，作者是这样解决的:

首先我们在 O(n) 中将这些数字的基数转换为 n，因此现在我们有最多 3 位数字(因为 n^3 )

现在我们使用基数排序，因此时间是 O(n)

所以我有三个问题:

1. 这是正确的吗？以及可能的最佳时间？

2. 如何在复杂度为 O(n) 的情况下转换 n 个数字的底数？像每个数字的 O(1)？因为本网站之前的一些主题说它的 O(M(n) log(n))？!

3. 如果这是真的，那么这意味着我们可以在 O(n) 中对从 0 到 n^m 的任何 n 个数字进行排序？!

( 我搜索了关于转换 n 个数字的基数，有人说它每个数字的 O(logn)，有些人说 n 个数字的 O(n)，所以我也对此感到困惑)

Answer 1

1) 是的，这是正确的。这是可能的最佳复杂性，因为任何排序都必须至少查看数字，即 O(n)。

2) 是的，每个数字都在 O(1) 中转换为 base-n。执行此操作的简单方法采用 O(m^2) 位数，通常假设您可以对最多 O(n) 的数字进行算术运算在O(1) 时间内。 m 是常数，所以 O(m^2) 是 O(1)...但实际上这一步只是说基数您在基数排序中使用的是 O(n)。如果您真正实现了这一点，您将使用 2 >= n 的最小幂，因此您不需要这些转换。

3) 是，如果 m 是常量。最简单的方法是将 m 传递到 LSB 优先基数排序中，基数约为 n。每次通过都需要 O(n) 时间，并且该算法需要 O(n) 额外内存(以可以容纳 n 的单词来衡量)。

所以作者是正确的。但实际上，这通常是从另一个方向进行的。如果您要编写一个对机器整数进行排序的函数，那么在某些较大的输入大小下，切换到基数排序会更快。如果 W 是最大整数大小，那么这个权衡点将是 n >= 2^(W/m) 对于某个常数 m . 这与您的约束条件相同，但清楚地表明我们只考虑大型输入。