4

有人可以带我了解以下问题解决方案的数学部分。

证明没有比较排序,其运行时间至少在 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
4

1 回答 1

6

这些证明中的每一个都是对更一般证明的直接修改,即你不能有一个排序比 Ω(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 n = lg n!- n = Ω(n log n) 也是如此,所以它不能在 O(n) 时间内排序。

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

希望这可以帮助!

于 2012-02-29T18:15:05.997 回答