这个问题在这里已有答案：
该定理表示：
任何比较排序算法在最坏的情况下执行Ω（nlg（n））比较 .
证明我发现：
查看算法执行的最差情况下的比较次数，意味着在其决策树中从根到叶的最长路径 .
作为高度为h的二叉树，最多有2 ^ h叶子，并且有n！排列（输出），我们有：
2 ^h≥n！
我知道我们可以将 2^h ≥ n! 重写为 h ≥ log2(n!) 但我们怎么能最终得到：
2^h ≥ n!
h ≥ log2(n!)
h≥log2（n！）=Ω（n * lg（n））？
N！是n个小于或等于n的数的乘积，因此：
log(n!) < log(n^n) => log(n!) < n*log(n)
和n！是n / 2数字的乘积，至少为n / 2，以及其他一些数字> 1，所以：
log(n!) > log((n/2)^(n/2)) => log(n!) > n*log(n/2)/2 => log(n!) > n*(log(n)-log(2))/2 => log(n!) > n*log(n)/4 when log(n) - log(2) > log(n)/2 => log(n!) > n*log(n)/4 when log(n) > 2log(2) => log(n!) > n*log(n)/4 when n > 4
将Stirling's approximation应用于log2（n！）项给出：
n log2（n） - log2（e）* n O（log2（n））
这是Ω（n log2（n））
2 回答
N！是n个小于或等于n的数的乘积，因此：
和n！是n / 2数字的乘积，至少为n / 2，以及其他一些数字> 1，所以：
将Stirling's approximation应用于log2（n！）项给出：
n log2（n） - log2（e）* n O（log2（n））
这是Ω（n log2（n））