我正在研究二进制、二项式和斐波那契堆排序，我发现排序需要 O(n log n) 时间。如果有人能给我一个理由来解释为什么会这样，那就太好了。
最佳答案
n 个元素的列表具有 n! 个排列。这些排列之一是正确排序的排列。两个元素之间的单次比较仅传达 1 位信息，因此不可能比将搜索空间减半更好。因此，区分正确排序的排列与所有其他排列所需的比较次数的下限是 log2(n!) ∈ O(n log n)。
请注意，log2(n!) 实际上只是一个下限 - 它并不意味着实际上可以用精确的 对 比较。事实上，有些排列需要您进行更多比较。但如果我们只对渐近行为感兴趣，这并不重要。n 数字进行排序上限(log2(n!))
所以你会看到，如果我们不限制自己使用基于比较的排序算法，下限就不成立。 (参见例如桶排序或基数排序。)
关于time-complexity - 为什么我们不能用比较排序算法比 O(n log n) 时间更快地对 N 个数字进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65054442/