通过比较排序的下界
今天我读了 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) 是有限的。
Today I was reading a great article from Julienne Walker about sorting - Eternally Confuzzled - The Art of Sorting and one thing caught my eye. I don't quite understand the part where the author proves that for sorting by comparison we are limited by Ω(N·log N) lower bound
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,1Notice 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).
It seems to be a very reasonable until the last part (bolded) which I don't quite understand - how log N! is equivalent to Ω(N·log N). I must be miss something from my CopmSci courses and can't get the last transition. I'm looking forward for help with this or for some link to other evidence that we are limited Ω(N·log N) if we use sorting by comparison.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您没有错过 CompSci 课程的任何内容。你错过的是数学课。斯特林近似的维基百科页面显示 log n!是渐近 n log n + 低阶项。
You didn't miss anything from CompSci class. What you missed was math class. The Wikipedia page for Stirling's Approximation shows that log n! is asymptotically n log n + lower order terms.
由此，您可以证明 θ(log N!) = O(N log N)。证明 Ω 的相同结果作为读者的练习，或者是 mathematics stackexchange 或 理论计算机科学 stackexchange。
With this, you can prove θ(log N!) = O(N log N). Proving the same for Ω is left as an exercise for the reader, or a question for mathematics stackexchange or theoretical computer science stackexchange.
我最喜欢的证明是非常基本的。
不！ = 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) 范围内的下界，这是超级小学，我可以说服普通高中。我什至无法推导出斯特林公式。我自己。
My favorite proof of this is very elementary.
N! = 1 * 2 * .. * N - 1 * N
We can can a very easy lower bound by pretending the first half of those products don't exist, and then that the second half are all just 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)
So even when you take only the second half of the expression, and pretend that all those factors are no bigger than N/2, you are still in O(n log n) territory for a lower bound, and this is super elementary. I could convince an average high school student of this. I can't even derive Stirling's formula by myself.