我正在研究二进制、二项式和斐波那契堆排序，我发现排序需要 O(n log n) 时间。如果有人能给我一个为什么会这样的理由，那就太好了。
问问题
147 次
1 回答
4
n元素列表具有n!排列。这些排列之一是正确排序的排列。两个元素之间的单个比较仅传达 1 位信息，因此不可能比将搜索空间减半更好。因此，区分正确排序的排列与所有其他排列所需的比较次数的下限是log2(n!) ∈ O(n log n)。
请注意，这log2(n!)实际上只是一个下限 - 这并不意味着实际上可以n通过精确ceiling(log2(n!))比较对数字进行排序。事实上，有些排列需要更多的比较。但是，如果我们只是对渐近行为感兴趣，这并不重要。
因此，您会看到，如果我们不将自己限制在基于比较的排序算法中，则下限将不成立。（参见例如桶排序或基数排序。）
于 2020-11-28T21:26:19.113 回答