顺序搜索

对于顺序搜索，在文件中查找记录所需的平均比较次数是多少？顺序搜索

来源

2010-03-06 neuromancer

A sequential search从文件的开头开始逐个检查每个元素，直到找到所需的元素。假设您正在搜索的记录只存在于文件中一次，并且可能在文件中的任何位置具有相同的概率，则平均比较次数等于文件中记录数量的一半。

但是，如果记录不存在于文件中，则在发现该文件之前，必须检查文件中的每个记录。

来源

2010-03-06 17:24:27

而且当值不在文件中时，记录所有记录的最坏情况。 – 2010-03-06 17:25:47

我也将它看作（n + 1）/ 2。为什么n + 1？ – neuromancer 2010-03-06 18:23:41

@Phenom：这是因为你可以从两个不同的假设开始。如果您假设您知道该条目在文件中，并且您只需要查找索引，则最小比较次数为1，最大次数为（n-1），平均值为（（n-1）+ 1）/ 2 = n/2。如果您假设您不知道条目在文件中的最小值为1，则最大值为n，因此在元素位于文件中时平均值为（n + 1）/ 2，并且n如果不是。 – 2010-03-06 18:39:35

对于包含n个项目的列表，最好的情况是该值等于列表的第一个元素，在这种情况下只需要一个比较。最坏的情况是该值不在列表中（或仅在列表末尾出现一次），在这种情况下需要进行n次比较。

Asymptotically，因此，最坏情况下的成本和线性搜索的预期成本都为O（n）

来源

2010-03-06 17:30:11

我想补充几点，以前的答案未能指出：

另一方面，我们必须考虑文件是在一台设备上可用还是分布在多台设备上。在T rams的情况下，复杂性将是O(T*N/(1+log(T)))。
一般来说，顺序搜索需要O(N) time complexity。
与R-Tree等数据结构结合使用时，在文件记录情况下，它可以给出O(N/(log(log(N))))的最佳时间复杂度。
它取决于文件的结构/格式，这样如果数据字段在哈希映射中可用，顺序搜索就是积压。

来源

2017-06-15 05:22:12

回答

相关问题