algorithm - 一小部分输入的比较排序下限？

Question

谁能指导我解决以下问题的数学部分。

证明不存在运行时间至少有一半是线性的比较排序 的!长度为 n 的输入。长度为 n 的输入的 1/n 的一小部分呢？ 分数 (1/(2)^n) 呢？

解决方法:

如果对于 m 个输入排列排序以线性时间运行，则排序的高度 h 决策树的一部分，由 m 个对应的叶子及其对应的叶子组成 祖先是线性的。 使用与定理 8.1 证明中相同的论证来证明这是不可能的 对于 m = n!/2、n!/n 或 n!/2n。 我们有 2^h ≥ m，这给了我们 h ≥ lgm。对于此处给出的所有可能的毫秒数， 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) 排序更快的比较排序(你可以看到这个证明 in this earlier answer )。直觉上，论证如下。为了使排序算法正常工作，它必须能够确定元素的初始顺序。否则，它无法对值重新排序以将它们按升序排列。给定 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)。

希望这对您有所帮助!