具體算法排序n個元素

Question

我要通過exercies用於算法分析考試，這是其中之一：

當前的算法，需要作爲輸入的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)。