考研帮 > 数学 > 每日一练

6.3 顺序查找法★2◎3

6.3 顺序查找法★2◎3

  顺序查找法又称线性查找法,是最基本的查找方法之一。其查找方法为:从表的一端开始,向另一端逐个按给定的值(key)与关键码进行比较。若找到,查找成功,并给出数据元素在表中的位置;若整个表检测完,仍未找到与key相同的关键码,则查找失败,给出失败信息。
  【顺序查找算法】

  

  【算法分析】
  对于n个数据元素的表,给定值key与表中第i个元素关键码相等,即定位第i个记录时,需进行n-i+1次关键码比较,即则查找成功时,顺序查找的平均查找长度为:

  设每个数据元素的查找概率相等,即,则等概率情况下有:

  查找不成功时,关键码的比较次数是n+1次,顺序查找的算法复杂度为O(n)。
  许多情况下,查找表中数据元素的查找概率是不相等的。为了提高查找效率,需要依据查找概率越高,比较次数越少;查找概率越低,比较次数就较多的原则来存储数据元素。
  顺序查找的缺点是当n很大时,平均查找长度较大,效率低;优点是对表中数据元素的存储没有要求。顺序查找适用于查找顺序存储或链式存储的线性表。
 

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭