algorithm - 找到一种时间复杂度为 O(n + k*log(k)) 的整数排序算法

Question

设计一个排序算法 有重复的整数。不同号码的总数为 k .您的算法应该具有时间复杂度 O(n + k*log(k)) .预计时间足够了。对于 的哪些值k 算法会变成线性吗？

我无法提出满足条件的整数排序算法 O(n + k*log(k)) .我不是一个非常高级的程序员，但在这个应该为所有数字提出算法之前我遇到了问题xi在列表中，0 ≤ xi ≤ m这样算法是 O(n+m)，其中 n 是列表中元素的数量，m 是列表中最大整数的值。我通过使用计数排序轻松解决了这个问题，但我在这个问题上很挣扎。对我来说最困难的条件是术语 k*log(k)如果是 n*log(n)，则在 ordo 符号下相反，我可以使用归并排序，对吗？但现在这是不可能的，所以任何想法都会非常有帮助。

提前致谢!

Answer 1

这是一个可能的解决方案:

使用哈希表，计算唯一值的数量和每个值的重复数量。这应该具有 的复杂性O(n) .

枚举哈希表，将唯一值存储到临时数组中。复杂性是 O(k) .

使用标准算法(例如归并排序)对这个数组进行排序:复杂度为 O(k.log(k)) .

通过复制存储在哈希表中的每个唯一值的排序数组的元素来创建结果数组。复杂性是 O(n) + O(k) .

组合复杂度为 O(n + k.log(k)) .

例如，如果 k 是一个小常数，对 的数组进行排序值向线性时间收敛为 变得越来越大。

如果在第一阶段，哪里 k 是增量计算的，看来 k 不明显小于 ，删除哈希表并使用标准算法对原始数组进行排序。