如果所有值都是正数且数字 <= k，我可以在 O(n) 中对数组进行排序吗？
Can I sort an array in O(n) if all values are positive and with digits <= k?
假设我有一个数组 A[1 ... n] ，除了它们是正数之外，它的值没有范围。如果我知道它们最多有 k 个数字，是否可以在 O(n) 中对数组进行排序？
我遇到的所有 O(n) 排序示例都给出了数组中值的上限。如果有重复请告诉我。
如果k <= n可以，否则不保证。
如果我给你n = 4和k = 5，你会把元素3放在哪里？
这取决于k是否为常数。
如果你的数字每个都有 k 位，那么你确实对数字有限制，因为它们不能大于 10k - 1。因此你可以使用 radix sort 对整数进行排序。基数排序的运行时间是 O((n + b)logb U)，其中 n 是要排序的数字的个数，b 是基数排序的基数，U 是您正在排序的最大值。在你的情况下，结果是
O((n + b) logb 10k) = O(k(n + b)).
这就是 "it depends" 的用武之地。如果 k 是某个永不改变的固定数字 - 例如，它始终为 137 或类似的数字 - 那么上面的表达式将简化为 O(n + b)，并选择 b 为任何常量（例如，基数排序的基数为 2）给出 O(n) 的运行时间。另一方面，如果 k 可以变化（比如，允许数字与您希望的一样大，然后在看到这些数字后您可以计算出 k 是多少），那么上面的表达式就不能被简化到 O(kn) 以上，因为 k 是算法的参数。
希望对您有所帮助！
假设我有一个数组 A[1 ... n] ，除了它们是正数之外，它的值没有范围。如果我知道它们最多有 k 个数字，是否可以在 O(n) 中对数组进行排序？
我遇到的所有 O(n) 排序示例都给出了数组中值的上限。如果有重复请告诉我。
如果k <= n可以，否则不保证。
如果我给你n = 4和k = 5，你会把元素3放在哪里？
这取决于k是否为常数。
如果你的数字每个都有 k 位，那么你确实对数字有限制，因为它们不能大于 10k - 1。因此你可以使用 radix sort 对整数进行排序。基数排序的运行时间是 O((n + b)logb U)，其中 n 是要排序的数字的个数，b 是基数排序的基数，U 是您正在排序的最大值。在你的情况下，结果是
O((n + b) logb 10k) = O(k(n + b)).
这就是 "it depends" 的用武之地。如果 k 是某个永不改变的固定数字 - 例如，它始终为 137 或类似的数字 - 那么上面的表达式将简化为 O(n + b)，并选择 b 为任何常量（例如，基数排序的基数为 2）给出 O(n) 的运行时间。另一方面，如果 k 可以变化（比如，允许数字与您希望的一样大，然后在看到这些数字后您可以计算出 k 是多少），那么上面的表达式就不能被简化到 O(kn) 以上，因为 k 是算法的参数。
希望对您有所帮助！