知识卡片

普通读书笔记卡 · 5654.c.1.a.2

比较排序下界依赖比较模型

理解等级:中级

当算法只能通过比较来区分一般输入的顺序时,需要足够多的比较结果识别可能的排列,最坏或相应平均情形存在nlogn量级下界。

这不是每个输入都必须做nlogn工作,也不限制利用受控整数值域等额外信息的方法。桶、计数和基数排序使用了不同前提,它们的成本必须把范围、桶数和位数算进去,不能说所有排序都无条件线性或无条件至少nlogn。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      此类排序算法的 时间复杂度无法超越 log 。接下来,我们将探讨几种“非比较排序算法” ,它们的时间复杂度可以达 到线性阶。 「桶排序bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[1665,1775)) - 结论依据:原文比较/非比较排序转折与后续值域限制,按模型限定过强说法。 - 原始内容:此类排序算法的 时间复杂度无法超越 log 。接下来,我们将探讨几种“非比较排序算法” ,它们的时间复杂度可以达 到线性阶。 「桶排序bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个