algorithm - 对具有 m 个不同值的 n 个元素进行排序的特定算法

Question

我正在为算法分析考试做练习，这是其中之一:

Present an algorithm that takes as input a list of n elements (that are comparable) and sorts them in O(n log m) time, where m is the number of distinct values in the input list.

我已经阅读了常见的排序算法，但我真的想不出一个解决方案。

谢谢你的帮助

Answer 1

您可以在 n 上构建一个增强的平衡二叉搜索树元素。存储在每个节点的增强信息将是它的频率。您使用 n 构建此结构插入到树中，执行此操作的时间为 O(n lg m) , 因为只有 m节点。然后你对这棵树进行中序遍历:访问左子树，然后打印存储在根节点的元素 f时代f是它的频率(这是增强信息)并最终访问正确的子树。此遍历需要时间 O(n + m) .因此，这个简单程序的运行时间为 O(n lg m + n + m) = O(n lg m)自 m <= n .