查找的基本概念（概念、查找算法的效率评价）

文章目录基本概念查找算法的评价指标总结基本概念查找—— 在数据集合中寻找满足某种条件的数据元素的过程称为查找若找到称为查找成功若表中不存在称为查找失败。查找表查找结构—— 用于查找的数据集合称为查找表它由同一类型的数据元素或记录组成它是一个集合元素间无明显的逻辑顺序除非特意有序。关键字—— 数据元素中唯一标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。(如id)主关键字唯一如学号可唯一识别一条记录次关键字不唯一如性别可识别多条记录。对查找表的常见操作①查找符合条件的数据元素静态查找表只支持查找/检索如顺序表【仅关注查找速度即可】②插入、删除某个数据元素动态查找表支持插入/删除如二叉排序树【除了查找速度也要关注插入、删除是否方便实现】查找算法的评价指标查找长度——在查找运算中需要对比关键字的次数称为查找长度平均查找长度ASL——所有查找过程中进行关键字的比较次数的平均值【ASL的数量级反应了查找算法时间复杂度】A S L ∑ i 1 n P i C i \boldsymbol{ASL\sum_{i1}^n P_i C_i}ASL∑i1n​Pi​Ci​n nn表中元素个数P i P_iPi​查找第 i 个元素的概率∑ P i 1 \sum P_i1∑Pi​1通常默认查找一个元素为等概率 -P i 1 n P_i\dfrac1nPi​n1​C i C_iCi​找到第 i 个元素需要比较关键字的次数查找长度【评价一个查找算法的效率时通常考虑查找成功 / 查找失败两种情况的ASL】总结