知识卡片

普通读书笔记卡 · 1292.g.1.b.1.a · 生成模型:未记录

顺序查找无需预先建立索引

理解等级:中级

从集合起点逐个检查元素,匹配时返回,迭代结束仍未匹配则报告不存在。它适用于小集合、单次查找或只有顺序访问的输入;代价最坏为 n 次比较,首次命中为常数,未命中必须检查所有元素。

多次查找时,排序或索引可能降低查询成本,但还要考虑构建和更新开销;比较单个元素本身的成本也可能不恒定。

110的图03242分别给出数组和迭代器版本,均在找到相等元素时返回true,耗尽后返回false;空集合自然返回false。

111指出仅能顺序遍历时适合顺序查找;如果允许额外构建索引或缓存,后续查询仍可能有其他方案,取决于访问和更新约束。

113展示Ruby、Java和C实现:Ruby使用each与==;Java调用元素equals,若元素为null会抛异常;C以比较函数返回0代表相等,示例中的ar与n需由上下文提供。

115在目标必定存在且每个位置等可能的前提下得到 (n+1)/2 次比较;有未命中概率时还要计入每次 n 次比较。最好首次命中 O(1),最坏 O(n);03248为特定实验的历史时间。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 5 处

    • · 查看原书依据

      顺序查找 顺序查找也叫做线性查找,是最简单的查询算法。它通过穷举来寻找集合C中的单独目标元素t。它从集合中的第一个元素开始查找,然后检查每一个随后的元素,知道匹配的元素查找到或者集合中每一个元素都被查找过。 考虑这样一个案例,一个中等规模的饭店有10~20张桌子可以被顾客预定。这个饭店靠近一个大型的

    • · 查看原书依据

      输入/输出 肯定有多种方法来从查找的集合中获取元素,顺序并不重要。如果一个集合A支持索引,那么能用索引值i来获得元素A[i]。一个集合C通常只能通过一个只读的迭代器来获得其中的每一个元素(例如,一个和SQL查询语句相关数据库的游标)。使用游标存取这些元素的方法在图5-1的下半部描述。 输入 输入包括

    • · 查看原书依据

      迭代器来存取,并且一次只能返回集合中的一个元素,那么顺序查找就是你能使用的唯一查找算法。

    • · 查看原书依据

      Ruby代码。 例5-1:Ruby的顺序查找 代码是如此的简单。这个函数的输入是一个集合和需要寻找的目标元素。集合可以是个数组或者是Ruby中任何一种能够支持each方法的集合。查找中的元素必须支持==操作符;否则的话,你需要使用Ruby支持的其他类型的相等操作符。例5-2是相同例子的Java实现。

    • · 查看原书依据

      平均情况下顺序查找(如我们在第2章所述)。 也就是说,对于每个目标元素来说,你将需要寻找集合中大约一半的元素。最好情况即待查找的元素是集合中的第一个。算法在最坏和平均情况下都是线性增长的。如果你加倍集合的大小,那么查找的时间也大约会是两倍。 为了得到顺序查找的实际性能,我们构造了一个包含n个整数(范

    参考来源

    - 位置:《算法技术手册》第5章《顺序查找》(spine1532;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1495.html;u109-ch05-002)。 - 结论依据:109全文及110的03242伪代码实读。 - 原始内容:顺序查找 顺序查找也叫做线性查找,是最简单的查询算法。它通过穷举来寻找集合C中的单独目标元素t。它从集合中的第一个元素开始查找,然后检查每一个随后的元素,知道匹配的元素查找到或者集合中每一个元素都被查找过。 考虑这样一个案例,一个中等规模的饭店有10~20张桌子可以被顾客预定。这个饭店靠近一个大型的 - 位置:《算法技术手册》第5章《输入/输出》(spine1532;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1495.html;u110-ch05-002)。 - 结论依据:110的图03242分别给出数组和迭代器版本,均在找到相等元素时返回true,耗尽后返回false;空集合自然返回false。 - 原始内容:输入/输出 肯定有多种方法来从查找的集合中获取元素,顺序并不重要。如果一个集合A支持索引,那么能用索引值i来获得元素A[i]。一个集合C通常只能通过一个只读的迭代器来获得其中的每一个元素(例如,一个和SQL查询语句相关数据库的游标)。使用游标存取这些元素的方法在图5-1的下半部描述。 输入 输入包括 - 位置:《算法技术手册》第5章《使用环境》(spine1533;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1496.html;u111-ch05-002)。 - 结论依据:111指出仅能顺序遍历时适合顺序查找;如果允许额外构建索引或缓存,后续查询仍可能有其他方案,取决于访问和更新约束。 - 原始内容:迭代器来存取,并且一次只能返回集合中的一个元素,那么顺序查找就是你能使用的唯一查找算法。 - 位置:《算法技术手册》第5章《解决方案》(spine1535;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1498.html;u113-ch05-002)。 - 结论依据:113展示Ruby、Java和C实现:Ruby使用each与==;Java调用元素equals,若元素为null会抛异常;C以比较函数返回0代表相等,示例中的ar与n需由上下文提供。 - 原始内容:Ruby代码。 例5-1:Ruby的顺序查找 代码是如此的简单。这个函数的输入是一个集合和需要寻找的目标元素。集合可以是个数组或者是Ruby中任何一种能够支持each方法的集合。查找中的元素必须支持==操作符;否则的话,你需要使用Ruby支持的其他类型的相等操作符。例5-2是相同例子的Java实现。 - 位置:《算法技术手册》第5章《分析》(spine1537;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1500.html;u115-ch05-002)。 - 结论依据:115在目标必定存在且每个位置等可能的前提下得到 (n+1)/2 次比较;有未命中概率时还要计入每次 n 次比较。最好首次命中 O(1),最坏 O(n);03248为特定实验的历史时间。 - 原始内容:平均情况下顺序查找(如我们在第2章所述)。 也就是说,对于每个目标元素来说,你将需要寻找集合中大约一半的元素。最好情况即待查找的元素是集合中的第一个。算法在最坏和平均情况下都是线性增长的。如果你加倍集合的大小,那么查找的时间也大约会是两倍。 为了得到顺序查找的实际性能,我们构造了一个包含n个整数(范