通过比较降低排序限制

Question

今天我正在阅读Julienne Walker关于排序的一篇很棒的文章 - Eternal Confuzzled - 排序艺术,有一件事引起了我的注意.我不太了解作者证明通过比较进行排序的部分我们受到Ω(N ·log N)下限的限制

下限不是那么明显.大多数排序算法的最低可能范围是Ω(N ·log N).这是因为大多数排序算法使用项目比较来确定项目的相对顺序.通过比较排序的任何算法将具有Ω的最小下界(N ·log N),因为比较树用于选择已排序的排列.可以很容易地构建三个数字1,2和3的比较树:

                         1 < 2

           1 < 3                       1 < 3

   2 < 3           3,1,2       2,1,3           2 < 3

1,2,3   1,3,2                            2,3,1     3,2,1

注意每个项目如何与每个其他项目进行比较,并且每个路径都会导致三个项目的有效排列.树的高度决定了排序算法的下限.因为有排列的算法是正确的,必须有尽可能多的叶子,比较树的最小可能高度登录ñ!,这相当于Ω(ñ ·日志ñ).

它似乎是一个非常合理的,直到最后一部分(粗体),我不太明白 - 如何记录N!等于Ω(N ·log N).我必须从我的CopmSci课程中遗漏一些东西,无法完成最后的过渡.如果我们通过比较使用排序,我期待着对此的帮助或者与我们有限的其他证据的链接Ω(N ·log N).

Answer 1

你没有错过CompSci课程的任何内容.你错过的是数学课.Stirling的近似的维基百科页面显示了log n!渐近n log n +低阶项.