This question already has answers here:
Is log(n!) = Θ(n·log(n))?
（9个答案）
定理表明：
任何比较排序算法在最坏情况下都执行Ω（nlg（n））比较。
为了证明我发现：
查找算法执行的最坏情况比较数，意味着在其决策树中从根到叶的最长路径。
作为一棵高度为h的二叉树，最多有2^h的叶子，并且有n排列（输出），我们有：
2^h≥n！
我知道我们可以将
h≥log2（n！）=Ω（n*lg（n））？
（9个答案）
定理表明：
任何比较排序算法在最坏情况下都执行Ω（nlg（n））比较。
为了证明我发现：
查找算法执行的最坏情况比较数，意味着在其决策树中从根到叶的最长路径。
作为一棵高度为h的二叉树，最多有2^h的叶子，并且有n排列（输出），我们有：
2^h≥n！
我知道我们可以将
2^h ≥ n!重写为h ≥ log2(n!)，但我们如何才能结束：h≥log2（n！）=Ω（n*lg（n））？
最佳答案
将Stirling's approximation应用于log2（n！）术语给出：
n log2（n）-log2（e）*n+O（log2（n））
即Ω（n log2（n））
关于algorithm - 排序算法复杂性的证明，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45108564/
10-11 04:37