algorithm - 设计一个对序列进行排序的算法 O(nloglogn)

Question

输入是一个包含许多重复项的 n 个整数序列，因此序列中不同整数的数量为 O(log n)。设计一个排序算法(仅基于比较)，在最坏情况下最多使用 O(n log log n) 次比较对此类序列进行排序。

有人可以解释为什么我应该使用红黑树而不是合并排序或其他一些排序算法。另外我怎么计算大o变成n log log n。

Answer 1

因为你使用的是红黑树，所以你在这棵树中插入了 log(n) ，你将只有不同的元素并记录每个元素的数量所以你只有 log(n) 个元素和它们的数量。要排序，您需要向树中插入 n 个元素，树的大小最大应为 log(n)，因此您需要 nlog(log(n)) 来处理整个事情，当您拥有树时，您可以简单地按排序顺序遍历它，将每个元素重复 k 次，其中 k 是元素计数。