七大查找算法之无序表查找---顺序查找

2021年3月31日 34点热度 0条评论 来源: 头脑灵活的胖子

静态查找表(Static Search Table):只作查找操作的查找表; 

动态查找表(Dynamic Search Table):在查找过程中同时插入不存在的元素,或者是删除已经存在的元素。

顺序查找

       顺序查找适合于存储结构为顺序存储或链接存储的线性表。

原理:

       顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

代码实现:

def sequenceSearch(arr,target):
    for i ,value in enumerate(arr):
        if value==target:
            return True
    return False
    

时间复杂度:

平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
Pi:查找表中第i个数据元素的概率
Ci:找到第i个数据元素时已经比较过的次数

       顺序查找成功时的平均查找长度为:(假设每个数据元素的概率相等)ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;当查找不成功时,需要n+1次比较,时间复杂度为O(n);所以,顺序查找的时间复杂度为O(n)

    原文作者:头脑灵活的胖子
    原文地址: https://blog.csdn.net/qq_30123335/article/details/83239400
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。