gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:55:03 27 4
gpt4 key购买 nike

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

证明不存在运行时间至少有一半是线性的比较排序的!长度为 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

最佳答案

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

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

希望这对您有所帮助!

关于algorithm - 一小部分输入的比较排序下限?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9304171/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com