当所有值都在 1 到 k 的范围内时,我们能否比基于比较的算法的 O(n lg n) 运行时间做得更好,其中 k < n。
计数排序和基数排序不是基于比较的算法,因此是不允许的。通过决策树分析,似乎有 k^n 种可能的排列。有 2^h 个叶子,所以应该可以在 O(n lg k) 时间内解决问题使用基于比较的排序算法。
请不要给出解决此问题的非基于比较的排序算法,所有排序都必须基于两个元素之间的比较。谢谢!
最佳答案
它可以很容易地在您指定的范围内完成。构建 k 个叶子的二叉树,并在每个叶子上包含一个计数值。如果使用合适的平衡算法,处理每个元素(添加它或增加计数)将是 O(lg k),因此完成所有这些将是 O(n lg k)。重建列表将是 O(n)。
关于algorithm - 1 到 k 范围内 n 个值的基于比较的排序的下限,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6615611/