search - 顺序搜索

Question

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

Answer 1

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

但是，如果文件中不存在该记录，则必须先检查文件中的每条记录，然后才能发现这一点。

Answer 2

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

因此，渐近地，线性搜索的最坏情况成本和预期成本都是 O(n)

Answer 3

我想补充几点，以前的答案没有指出：

• 另一方面，我们必须考虑文件是在一个设备上可用还是分布在多个设备上。在 T rams 的情况下，复杂度将为O(T*N/(1+log(T))).

• 一般来说，顺序搜索需要O(N) time complexity.

• 当与 R-Tree 等数据结构结合使用时，它可以提供O(N/(log(log(N))))文件中记录的最佳情况时间复杂度。

• 它取决于文件的结构/格式，因此如果数据字段在哈希映射中可用，则顺序搜索是一个积压。