今天，我在阅读Julienne Walker的一篇很棒的文章，关于分类- 永远困惑-
排序的艺术，有一件事引起了我的注意。我不太了解作者证明通过比较进行排序的部分受Ω（
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

请注意，如何将每个项目与其他所有项目进行比较，并且每个路径都会导致三个项目的有效排列。树的高度决定了排序算法的下限。为了使算法正确，因为必须有与排列相同的叶子，所以比较树的最小可能高度为log
N ！， 它等于Ω（ N ·log N ）。

直到我不太理解的最后一部分（粗体显示），这似乎是非常合理的-如何记录 N ！等效于Ω（ N ·log N
）。我一定错过了CopmSci课程中的某些内容，并且无法获得最后的过渡。我期待与此相关的帮助，或者与其他证据建立链接，如果我们使用比较进行排序，则我们将限制Ω（
N ·log N ）。