知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2 · 生成模型:未记录

有序搜索要计入预处理代价

理解等级:中级

排序把全体数据按约定排列,搜索则定位某个目标,两者不是同一任务。若数据较稳定且要反复查询,可先排序,再用要求有序的搜索方法;若每次查询前数据都大改,维护有序性的代价也必须计入。

线性搜索只需按可访问次序逐项比较,链表不支持高效随机下标时常用它;二分查找利用有序范围缩减候选,还需考虑定位中点的访问成本。本节只预告机制,具体边界由后续实现展开。

次序统计问第i小元素,完整排序后取第i项是一种方法,却可能为只取一个名次做了多余工作。本书此处未给选择算法,不把排序说成唯一途径。

221数据变更需维持compare对应的顺序,否则排除半区的推理失效。原文“连续空间必须”是本实现表示条件,不是任意二分逻辑的数学必要条件;静态不自动意味任何工作负载都最佳。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      数据集不变时,二分搜索的应用效果最佳。 排序和搜索算法的一些应用: 次序统计 寻找集合中第i小的元素。一个简单的方法就是,一旦数据集排好序,取出第i个元素即可。 二分搜索 一种有效的查找方法,它依赖于有序数据集。二分搜索不断地将数据集从中分段,并检查每段中心位置的元素,从而最终找到目标元素。 目录列

    • · 查看原书依据

      频繁进行插入和删除操作的数据集时不太高效。这是因为,对于插入和删除操作来说,为了保证查找过程正常进行,必须保证数据集始终有序。相对于查找来说,维护一个有序数据集的代价更高。此外,元素必须存储在连续的空间中。因此,当待搜索的集合是相对静态的数据集时,此时使用二分查找法是最好的选择。

    参考来源

    - 位置:《算法精解:C语言描述》第12章《第12章 排序和搜索》(spine1337;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1303_split_001.html;u204-ch12-003)。 - 结论依据:204搜索定义、二分静态数据说明和次序统计应用全文实读,明确排序预处理/动态维护与访问模型,不增加未给选择算法实现。 - 原始内容:数据集不变时,二分搜索的应用效果最佳。 排序和搜索算法的一些应用: 次序统计 寻找集合中第i小的元素。一个简单的方法就是,一旦数据集排好序,取出第i个元素即可。 二分搜索 一种有效的查找方法,它依赖于有序数据集。二分搜索不断地将数据集从中分段,并检查每段中心位置的元素,从而最终找到目标元素。 目录列 - 位置:《算法精解:C语言描述》第12章《二分查找的描述》(spine1353;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1319.html;u221-ch12-003)。 - 结论依据:221数据变更需维持compare对应的顺序,否则排除半区的推理失效。原文“连续空间必须”是本实现表示条件,不是任意二分逻辑的数学必要条件;静态不自动意味任何工作负载都最佳。 - 原始内容:频繁进行插入和删除操作的数据集时不太高效。这是因为,对于插入和删除操作来说,为了保证查找过程正常进行,必须保证数据集始终有序。相对于查找来说,维护一个有序数据集的代价更高。此外,元素必须存储在连续的空间中。因此,当待搜索的集合是相对静态的数据集时,此时使用二分查找法是最好的选择。