对于一小部分输入的比较排序的下限？

Question

有人可以告诉我解决以下问题的数学部分.

显示没有比较排序,其运行时间至少是n的一半是线性的!长度为n的输入.那么长度为n的输入的1/n的一小部分呢？分数(1 /(2)^ n)怎么样？

解:

如果排序在m个输入排列的线性时间内运行,那么由m个相应叶子和它们的祖先组成的决策树部分的高度h是线性的.使用与定理8.1的证明中相同的参数来表明m = n!/ 2,n!/ n或n!/ 2n是不可能的.我们有2 ^h≥m,这给我们h≥lgm.对于此处给出的所有可能的ms,lgm =Ω(n lg n),因此h =Ω(n lg n).特别是,

    lgn!/2= lg n! ? 1 ? n lg n ? n lg e ? 1
    lgn!/n= lg n! ? lg n ? n lg n ? n lg e ? lg n
    lgn!/2^n= lg n! ? n ? n lg n ? n lg e ? n

Answer 1

这些证明中的每一个都是对更一般证据的简单修改,即您无法进行比Ω更快排序的比较排序(n log n)(您可以在此前面的答案中看到此证明).直觉上,论点如下.为了使排序算法正常工作,它必须能够确定元素的初始排序.否则,它无法重新排序值以按升序排列.给定n个元素,有n个!这些元素的不同排列,意味着有n!排序算法的不同输入.

最初,算法对输入序列一无所知,也无法区分任何n!不同的排列.每次算法进行比较时,它都会获得有关元素排序方式的更多信息.具体地,它可以判断输入置换是在比较产生为真的排列组中还是在比较产生假的排列组中.您可以直观地看出算法如何作为二叉树工作,其中每个节点对应于算法的某个状态,并且特定节点的(最多)两个子节点指示如果比较产生真值将输入的算法的状态或者是假的.

为了使排序算法能够正确排序,它必须能够为每个可能的输入输入唯一的状态,因为否则算法无法区分两个不同的输入序列,因此会对它们中的至少一个进行排序不正确.这意味着如果考虑树中的叶节点数(算法已完成比较并将要排序的部分),则每个输入排列必须至少有一个叶节点.在一般证据中,有n!排列,所以必须至少有n!叶节点.在二叉树中,拥有k个叶子节点的唯一方法是使高度至少为Ω(log k),这意味着您必须至少进行Ω(log k)比较.因此,通过斯特林的近似,一般排序下限是Ω(log n!)=Ω(n log n).

在您考虑的情况下,我们将自己限制在那些可能的排列的子集中.例如,假设我们希望能够排序n!/ 2的排列.这意味着我们的树的高度必须至少为lg(n!/ 2)= lg n! - 1 =Ω(n log n).结果是.你不能按时间O(n)排序,因为没有线性函数以Ω(n log n)的速率增长.对于第二部分,看看你是否能得到n!/ n按线性时间排序,决策树必须有高度lg(n!/ n)= lg n! - lg n =Ω(n log n),因此您无法对O(n)比较进行排序.对于最后一个,我们有那个lg n!/ 2 ⁿ = lg n! - n =Ω(n log n),因此再次无法在O(n)时间内进行排序.

但是,您可以在线性时间内排序2 ⁿ个排列,因为lg 2 ⁿ = n = O(n).

希望这可以帮助!