具有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.