algorithm - 1 到 k 范围内 n 个值的基于比较的排序的下限

Question

当所有值都在 1 到 k 的范围内时，我们能否比基于比较的算法的 O(n lg n) 运行时间做得更好，其中 k < n。

计数排序和基数排序不是基于比较的算法，因此是不允许的。通过决策树分析，似乎有 k^n 种可能的排列。有 2^h 个叶子，所以应该可以在 O(n lg k) 时间内解决问题使用基于比较的排序算法。

请不要给出解决此问题的非基于比较的排序算法，所有排序都必须基于两个元素之间的比较。谢谢!

Answer 1

它可以很容易地在您指定的范围内完成。构建 k 个叶子的二叉树，并在每个叶子上包含一个计数值。如果使用合适的平衡算法，处理每个元素(添加它或增加计数)将是 O(lg k)，因此完成所有这些将是 O(n lg k)。重建列表将是 O(n)。