algorithm - 我们可以对具有 O(n) 空间复杂度的 n 个元素进行计数排序算法吗？

Question

我今天参加了期中考试，其中一个算法问题是“我们能否为计算 n 个元素的排序 O(n) 计算空间复杂度”。实际上我找不到任何解决方案。有没有人知道任何算法或数据结构。我想知道答案并考虑一下。非常感谢。

标签： algorithmsortingcounting

Answer 1

如果我们在计数排序中使用数组进行计数，那么它需要的空间等于最大和最小键值之间的差。我们可以使用哈希表，然后我们可以将空间复杂度降低到相对于输入中元素数量的线性。但在这种情况下，隐藏常数可能太大，性能可能会下降。