algorithm - 使用 O(k) 内存的 O(N) 运行时间哈希

Question

所以假设我们有一个 m 数字数组，这个数组中的最大数字是 k。此数组中有重复项。

let array a = [1,2,3,1,2,5,1,2,3,4]

是否有一种算法可以在 o(n) 次操作后打印出此数组 [1,2,3,4,5](均已排序且无重复)，其中 n 是唯一值的数量。

我们可以使用k 内存——在本例中为5。 我想到的算法是使用哈希表。将值插入到哈希表中，如果该值之前存在，我们将忽略它。这将自动排序。但是，如果我们有 5 个数字，[1,2,3,100,4] 但其中一个是 100，这意味着当打印这 5 个数字时，我们需要运行 o(k) ~= 100 次而不是 o(n) ~= 5 次。 有没有办法解决这个问题？

Answer 1

我不认为存在这样的算法。看这里https://en.wikipedia.org/wiki/Sorting_algorithm

本质上，对于基于比较的算法，您可以达到的最佳效果是 O(nlogn)。但是由于您提供了最大值 k，我认为您想要的不仅仅是基于比较的算法。

但对于非基于比较的算法，由于它本质上取决于数字的大小，复杂度必须反射(reflect)这种依赖性 - 这意味着您的总时间复杂度中肯定会有 k。您将无法找到仅 O(n) 的算法。

相反，如果该O(n) 算法存在并且不依赖于k。您可以对任何 n 数字数组进行排序，因为 k 是额外的无用信息。