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

Question

我正在通过算法分析考试的练习，这是其中之一：

提出一种算法，该算法将 n 个元素（可比较）的列表作为输入，并在 O(n log m) 时间内对它们进行排序，其中 m 是输入列表中不同值的数量。

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

谢谢你的帮助

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.