网站建设性能指标,网页结构有哪几种,滨海网站建设找哪家好,湖南宏点文化传媒有限公司知识总览#xff1a; 顺序查找#xff1a;
算法思想#xff1a;
从头到脚挨个找或者从脚到头挨个找适用于线性表(顺序存储和链式存储都适用)#xff0c;又叫线性查找 实现#xff1a;
1个数组elem指向数组的起始位置#xff0c;索引从0开始遍历数组直到找到目标值返回…知识总览 顺序查找
算法思想
从头到脚挨个找或者从脚到头挨个找适用于线性表(顺序存储和链式存储都适用)又叫线性查找 实现
1个数组elem指向数组的起始位置索引从0开始遍历数组直到找到目标值返回索引下标否则返回-1 顺序查找-添加哨兵
数组的第一个位置不存数据而是在查找的时候放目标值即哨兵从索引1开始存放数据然后从数组长度倒序查找比较目标值如果找到目标值则返回索引下标如果返回索引0证明没找到目标值添加哨兵是为了避免数组越界发现到了哨兵的位置就不再查找 查找效率分析
评价一个查找算法要看平均查找长度即ASL平均查找长度又分查找成功和查找失败
假设找任何一个关键字的概率都是相同的如果一共有n个关键字假设找最后一个关键字则概率为1/n如果找倒数第2个关键字则需要对比2次则找到的概率为2* 1/n依次类推需要比较n次则平均查找长度为(123...n)/n(n1)/2,查找失败为查找所有的数据都没有查找到即比较了n1次(有加1是因为哨兵还占了一个位置)即查找成功和查找失败的时间复杂度都为O(n) 顺序查找的优化(对有序表)
就是因为顺序查找是挨个找所以假如要查找的数组数据开始有顺序的话就方便查找视频中说得有n1种失败的情况不知道从哪来的可能是跟上边查找效率分析有关把每次失败都加了区间范围然后根据n1种失败的情况再确定每次失败的概率为1/n1第2段要比较2次失败的概率为2*(1/n1)。。。。。直到到如下数组中第n个数因为n前后有2个范围段所以加了2次n最后得到ASLn/2(n1)/n 用查找判定树分析ASL
方形节点为失败节点圆形节点为成功节点 如果要找的关键字在圆形节点即成功节点中要付出的查找长度(关键字的对比次数)自身所在的层数比如要找关键字19要进行7,13,19三次对比失败节点的查找长度父节点所在层数假如关键字在13-19方形区间直到确认失败需要对比7、13、19三次即父节点所在层数(就是圆形节点所在层数吗) 顺序查找的优化(被查概率不相等)
每个关键字的查找概率不相等假如查找成功的概率大就把被查概率大的放前面有助于在查找成功时缩短ASL但是此时数组的数据乱序即可以提高查找成功的平均查找长度但是查找失败的情况需要从头扫到尾才知道查找失败了即查找失败的平均查找长度ASL非常大故具体问题具体分析
不管怎么优化只要采用顺序查找时间复杂度就是O(n) 知识回顾 听不懂在讲什么。。。。。。。。。
