知识卡片

普通读书笔记卡 · 5654.d.1.a.5

预处理成本要按查询摊算

理解等级:中级

有序且可快速定位中点时,二分查找能用少量比较缩小候选。但为了单次查询先排序,可能比直接线性扫描更贵;若后续查询很多,预处理就可能被摊薄。

频繁插入维护有序又有更新成本,因此结构选择需看查询次数、更新频率和内存预算。二分也能作用于单调谓词或可计算虚拟序列,并非只能实体数组;小输入谁更快仍须具体实现与环境测量。

搜索章进一步把线性、二分、哈希与树按查询、更新、顺序和空间比较。范围查询通常更依赖有序索引,精确键查询可用哈希;数据能否容纳还取决于布局、外部存储和预算,不能简单断言树适合任意海量、数组或哈希不适合大数据。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      为了使用二分查找而专门进行排序,得不偿失。因为 排序算法的时间复杂度通常为 log ,比线性查找和二分查找都更高。对于频繁插入元素的场景, 为保持数组有序性,需要将元素插入到特定位置,时间复杂度为 ,也是非常昂贵的。 ‧

    • · 查看原书依据

      搜索算法的选择还取决于数据体量、搜索性能要求、数据查询与更新频率等。 线性搜索 ‧ 通用性较好,无须任何数据预处理操作。假如我们仅需查询一次数据,那么其他三种方法的数据预处理 的时间比线性搜索的时间还要更长。 ‧ 适用于

    参考来源

    - 位置:《Hello 算法--Go版本》第10章《搜索》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[11183,11293)) - 结论依据:实际二分局限与成本解释,纠正预排序永远不值及仅数组/小量总更快的绝对话。 - 原始内容:为了使用二分查找而专门进行排序,得不偿失。因为 排序算法的时间复杂度通常为 log ,比线性查找和二分查找都更高。对于频繁插入元素的场景, 为保持数组有序性,需要将元素插入到特定位置,时间复杂度为 ,也是非常昂贵的。 ‧ 补充原书证据:spine 4 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;归一字符[17990,18100)。 - 结论依据:实际方法选取四类条件,保留成本总账不沿用数据量绝对分类。 - 原始内容:搜索算法的选择还取决于数据体量、搜索性能要求、数据查询与更新频率等。 线性搜索 ‧ 通用性较好,无须任何数据预处理操作。假如我们仅需查询一次数据,那么其他三种方法的数据预处理 的时间比线性搜索的时间还要更长。 ‧ 适用于