比较排序O(nlogn)推导：维基百科对数不等式的指数疑问

首先拆解这个不等式的核心逻辑：

• n! = 1×2×3×…×(n/2)×(n/2+1)×…×n，我们把它拆成前n/2项和后n/2项两部分。
• 后n/2项里的每一个数（从n/2+1到n），都严格大于等于n/2。比如n=6时，后3项是4、5、6，都≥3（即n/2）。
• 这n/2个大于等于n/2的数相乘，结果必然≥(n/2)重复乘n/2次——也就是(n/2)^(n/2)。
• 而n!是前n/2项（正数）乘以后n/2项，所以n! ≥ 后n/2项的乘积 ≥ (n/2)^(n/2)。对两边取单调递增的log₂，不等号方向不变，就得到log₂(n!) ≥ log₂((n/2)^(n/2))。

再说说为什么选这个变体而不是其他形式：
我们的目标是证明比较排序的时间复杂度下界是Ω(nlogn)，而比较排序的决策树高度至少是log₂(n!)（因为n个元素有n!种排列，决策树至少需要log₂(n!)个节点层级才能覆盖所有情况）。所以需要找到log₂(n!)的下界，且这个下界要能归约到nlogn量级。

把log₂((n/2)^(n/2))展开计算：

log₂((n/2)^(n/2)) = (n/2) × log₂(n/2)
                  = (n/2)(log₂n - log₂2)
                  = (n/2)log₂n - n/2

这里的主导项是(n/2)log₂n，显然属于Ω(nlogn)。由此可以推导出log₂(n!)也是Ω(nlogn)，结合比较排序的上界O(nlogn)（比如归并排序、堆排序），就能得出比较排序的时间复杂度是Θ(nlogn)，也就是书中说的通常为O(nlogn)。

其他变体要么难以计算到nlogn量级，要么无法提供足够紧的下界来支撑这个结论，所以这个形式是推导中最简洁有效的选择。

内容的提问来源于stack exchange，提问作者Ythene