Lowed开往通过对比排序 [英] Lowed bound for sorting by comparison

问题描述

今天，我在读从朱利安·沃克一大篇有关排序 - 永恒Confuzzled - 排序的艺术有一件事引起了我的眼睛。我不太明白的部分在这里笔者证明，通过比较，我们的排序是由Ω（ N 的·登录的 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

下界并不明显。最低界最排序算法是Ω（ N 的·登录的 N 的）。这是因为大多数的排序算法使用项目比较，以确定物品的相对顺序。任何算法的排序由比较将具有最小下界Ω的（ N 的·登录的 N 的），因为比较树用于选择真实排序的置换。对于三个数字的比较树1，2和3可以很容易地构造：

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

     

请注意每一个项目与所有其他项目相比，认为每个路径导致三个项目的有效置换。树的高度决定下界排序算法。因为必须有尽可能多的叶片为有排列为算法是正确的，则比较树的最小可能高度为日志的 N 的!,的这相当于Ω（的 ñ的·登录的 N 的）

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).

这似乎是一个非常合理的，直到最后一部分（加粗），我不太明白 - 怎么记录的 N 的！相当于Ω（ N 的·登录的 N 的）。我必须为我的CopmSci课程错过的东西并不能获得最后的过渡。我期待着帮助，这或对一些链接到其他的证据，我们是有限的Ω（ N 的·登录的 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.

推荐答案

您没有错过CompSci类的东西。你错过了什么是数学课。维基百科页面斯特灵公式表明，日志N！渐近N日志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.

这篇关于Lowed开往通过对比排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！