Title Date Modified Category
searching 2019-07-09 12:00 2019-07-09 12:00 algorithm

1.1. 顺序表查找

顺序查找(Sequential Search)又叫线性查找,是最基本的查找技术,它的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录;如果直到最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查的记录,查找不成功。

对于这种顺序查找算法来说, 查找成功最好的情况就是第一个位置就找到了,算法时间复杂度为O(1), 最坏的情况是在最后一位置才找到,需要n次比较,时间复杂度为O(n), 当查找不成功时,需要n+1次比较,时间复杂度为O(n)。 我们之前推导过,关键字在任何一位置的概率是相同的,所以平均查找次数为(n+1)/2, 所以最终时间复杂度还是O(n)。

results matching ""

    No results matching ""