比较排序的下限界

Question

今天我在阅读Julienne Walker关于排序的一篇优秀文章 - Eternally Confuzzled - The Art of Sorting，其中有一点引起了我的注意。我不太理解作者证明用比较进行排序时，我们受到Ω(N·log N)下限的限制部分。

Lower bounds aren't as obvious. The lowest possible bound for most sorting algorithms is Ω(N·log N). This is because most sorting algorithms use item comparisons to determine the relative order of items. Any algorithm that sorts by comparison will have a minimum lower bound of Ω(N·log N) because a comparison tree is used to select a permutation that's sorted. A comparison tree for the three numbers 1, 2, and 3 can be easily constructed:

                         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

Notice how every item is compared with every other item, and that each path results in a valid permutation of the three items. The height of the tree determines the lower bound of the sorting algorithm. Because there must be as many leaves as there are permutations for the algorithm to be correct, the smallest possible height of the comparison tree is log N!, which is equivalent to Ω(N·log N).

这篇文章看起来非常合理，直到最后一部分（加粗的内容），我不太理解——如何将log N！等价于Ω（N·log N）。我可能在我的计算机科学课程中遗漏了什么，无法理解最后的过渡。我期待着对此进行帮助，或者提供其他证据的链接，以证明如果我们使用比较排序，我们受到Ω（N·log N）的限制。

- Andrey Taptunov

Answer 1

您在计算机科学课上并没有错过任何东西。您错过的是数学课。斯特林近似公式的维基百科页面显示，对数 n！渐近于 n log n 加低阶项。

- Raymond Chen

Answer 2

• N! < N^N
• ∴ log N! < log (N^N)
• ∴ log N! <N * log N

有了这个，您可以证明 θ(log N!) = O(N log N)。对于 Ω 的证明留给读者作为练习，或者您可以在 数学交流 或 理论计算机科学交流 上提问。

- bdonlan

---

但是这个不等式的方向是错误的。你想要确保log(N!) > （以O(n log n)增长的某些值）。你需要证明任何基于比较的算法必须至少进行这么多次比较。 - Rob Neuhaus

正如我所说，“证明Ω的相同情况留给读者作为练习”，并在给出提示后，将OP引荐到更相关的stackexchanges主题。 - bdonlan

Answer 3

我的最爱证明非常基础。

N! = 1 * 2 * .. * N - 1 * N

我们可以通过假装这些乘积的前一半不存在，然后将后一半都视为N/2，得到一个非常简单的下限。

(N/2)^(N/2) <= N!

log((N/2)^(N/2) = N/2 * log(N/2) = N/2 * (log(N) - 1) = O(n log n)

因此，即使您仅考虑表达式的后半部分，并假装所有这些因子都不大于N/2，您仍然处于O（n log n）领域中，这是超级基础的。我可以说服一个普通的高中生相信这个结论。 我甚至不能自己推导斯特林公式。

- Rob Neuhaus

---

很好的“信封背面”方法，每个人都应该知道。 - dhruvbird