首页 文章

理解基于比较的排序算法的下界

提问于
浏览 次
-1

首先，我知道

  • 下限是O（nlogn）

  • 以及如何证明它

我同意下限应该是O（nlogn） .

我不太明白的是：

对于某些特殊情况，比较数实际上甚至可能低于下限 . 例如，使用冒泡排序对已排序的数组进行排序 . 比较数是O（n） .

So how to actually understand the idea of lower bound?

维基百科的经典定义：http://en.wikipedia.org/wiki/Upper_and_lower_bounds没有多大帮助 .

我目前对此的理解是：

lower bound of the comparison-based sorting is actually the upper bound for the worst case.

也就是说，在最坏的情况下你能做到最好 .

它是否正确？谢谢 .

algorithm sorting lower-bound

4 回答

  • 1

    基于比较的排序的下限实际上是最佳情况的上限 .

    号

    您绑定的函数是 best possible 排序算法的 worst-case 运行时间 .

    想象一下以下游戏：

    • 我们选择一些数字n .

    • 您选择自己喜欢的排序算法 .

    • 在查看算法后，我选择了一些长度为n的输入序列 .

    • 我们在输入上运行你的算法，你为每个执行的指令给我一美元 .

    O（n log n）上限意味着无论我选择什么输入序列，您都可以将成本限制为最多O（n log n）美元 .

    Ω（n log n）下限意味着无论您选择何种排序算法，我都可以强制您支付至少Ω（n log n）美元 .

    Also: "The lower bound is O(n log n)"没有任何意义 . O（f（n））表示"at most a constant times f(n)" . 但"lower bound"表示"at least ..." . 所以说"a lower bound of O(n log n)"就像说“你可以保存 up to 50％ or more ！” - 这完全没有意义！下限的正确表示法是Ω（...） .

    回复于
  • 0

    排序问题可以看作如下 .

    输入：n个数字的序列 . 输出：输入序列的置换（重新排序），使得a'1 <= a'2 ...... .. <= a'n .

    如果排序算法使用比较运算符来查找两个数字之间的顺序，则排序算法是基于比较的 . 可以根据决策树抽象地查看比较排序 . 决策树是完整的二叉树，表示由对给定大小的输入进行操作的特定排序算法执行的元素之间的比较 . 排序算法的执行对应于跟踪从决策树的根到叶的路径 . 在每个内部节点处，进行比较ai aj . 然后左子树指示ai aj的后续比较，右子树指示ai> aj的后续比较 . 当我们来到一片叶子时，排序算法已经 Build 了排序 . 所以我们可以说关于决策树 .

    1）每个n！ n个元素的排列必须作为决策树的一个叶子出现，以便排序算法正确排序 .

    2）令x为排序算法中的最大比较数 . 决策树的最大高度为x . 具有最大高度x的树具有至多2 ^ x个叶子 .

    结合以上两个事实，我们得到以下关系 .

    n!  <= 2^x

    登录两侧 . \ log_2n！ <= x

    自\ log_2n！ = \ Theta（nLogn），我们可以说x = \ Omega（nLog_2n）因此，任何基于比较的排序算法必须至少进行\ Omega（nLog_2n）比较才能对输入数组进行排序，而Heapsort和merge排序是渐近最优的比较排序 .

    回复于
  • 0

    当您进行渐近分析时，您为所有输入派生 O 或 Θ 或 Ω .
    但您也可以分析输入的属性是否会影响运行时 .
    例如，由于输入特性和算法的结构，将几乎排序的输入作为输入的算法比正式渐近公式具有更好的性能 . 例如bubblesort和quicksort .
    并不是说你可以贬低下边界 . 它只对特定输入的实现行为 .

    回复于
  • 5

    想象一下可以排序的所有可能的事物阵列 . 让我们说它们是长度为'n'的数组，并忽略像带有一个元素的数组（当然，它们总是已经排序了） .

    想象一下该阵列的所有可能值组合的长列表 . 请注意，我们可以稍微简化一下，因为数组中的值总是有某种排序 . 因此，如果我们用数字1替换最小的一个，下一个用1或2（取决于它是等于还是更大）等等，我们最终会遇到相同的排序问题，就像我们允许任何值一样所有 . （这意味着长度为n的数组最多需要数字1-n . 如果某些数字相等，则可能更少 . ）

    然后在每个数字旁边放一个数字，说明用这些值对数组进行排序所需的工作量 . 你可以放几个数字 . 例如，您可以进行比较次数 . 或者你可以把元素移动或交换的数量 . 无论你输入什么数字，都表明它需要多少次操作 . 你可以把它们的总和 .

    你要做的一件事是忽略任何特殊信息 . 例如，您无法提前知道数组中值的排列已经排序 . 您的算法必须与该数组执行与其他任何数组相同的步骤 . （但第一步可能是检查它是否已排序 . 通常这对排序没有帮助 . ）

    所以 . 通过比较测量的最大数字是当以病态恶劣的方式排列值时的典型比较次数 . 类似地，最小的数字是当以非常好的方式排列值时所需的比较的数量 .

    对于冒泡排序，最好的情况（最短或最快）是如果值已经按顺序排列 . 但只有当你使用一个标志来判断你是否交换了任何值时 . 在这种最好的情况下，你可以一次查看每对相邻元素并发现它们已经排序，当你到达最后时，你会发现你没有交换任何东西，所以你已经完成了 . 这是n-1比较的总和，并形成你可以做的最低比较数 .

    我需要一段时间来弄清楚最糟糕的情况 . 几十年来我没有看过泡泡类别 . 但我猜它是一个反向排序的情况 . 你进行第一次比较，发现第一个元素需要移动 . 与每个元素相比，您向上滑动到顶部，最后将它与最后一个元素交换 . 所以你在那个传球中进行了n-1次比较 . 第二遍从第二个元素开始并进行n-2次比较，依此类推 . 所以你做（n-1）（n-2）（n-3）... 1比较在这种情况下约为（n ** 2）/ 2 .

    也许你对冒泡排序的变化比我描述的更好 . 不管 .

    对于冒泡排序，下限为n-1，上限为（n ** 2）/ 2

    其他排序算法具有更好的性能 .

    您可能想要记住除了比较之外还有其他操作需要花费 . 我们使用比较，因为使用字符串进行了大量排序，并且字符串比较在计算时间上是昂贵的 .

    您可以使用元素交换计数（或交换和元素交换的总和），但它们通常比与字符串的比较短 . 如果你有数字，它们是相似的 .

    您还可以使用更多深奥的东西，如分支预测失败或内存缓存未命中或测量 .

    回复于

相关问题