查找算法的评价指标 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数 第11页
第 11 页 查找成功:最少比较次数 最多比较次数 平均比较次数 查找失败:最少比较次数 最多比较次数 平均比较次数 查找算法的评价指标
查找算法的平均查找长度ASL (Average Search Length 指为了确定记录在查找表中的位置,需 要和给定值进行关键字比较的次数的期望值: ASL=∑PC 其中,n为表长,P为查找表中第个记录的 概率,且∑P=1;C为査找到该记录时,曾和 给定值进行关键字比较的次数。 第12页
第 12 页 查找算法的平均查找长度ASL (Average Search Length) 指为了确定记录在查找表中的位置，需 要和给定值进行关键字比较的次数的期望值: = = n i ASL Pi Ci 1 其中，n为表长，Pi为查找表中第i个记录的 概率，且 ；Ci为查找到该记录时，曾和 给定值进行关键字比较的次数。 1 1 = = n i Pi
在等概率情形,查找仼一记录的概率 相等:p1=1/n,i=1,2,…,n 以从前向后顺序查找算法为例 查找成功时, ASL 1:1n(n+1)n+1 二 查找不成功时, ASL n=n CC 查找算法时间复杂度?O(n) 第13页
第 13 页 . ( ) = + = + = = n i succ n n n n i n ASL 1 2 1 2 1 1 1 在等概率情形，查找任一记录的概率 相等：pi = 1/n, i = 1, 2, , n ➢查找不成功时， ➢查找成功时， 以从前向后顺序查找算法为例， 查找算法时间复杂度？ O(n) = = = n i unsucc n n n ASL 1 1
顺序查找算法总结 ·查找长度: 查找成功:最少比较次数 最多比较次数n 平均比较次数(n+1)/2 查找失败最少比较次数n 最多比较次数n 平均比较次数n 优点:查找结构无特殊要求(线性结构均适 用);算法简单; 缺点:查找效率较低,不适于大表查找。 第14页
顺序查找算法总结 • 查找长度： 查找成功:最少比较次数 1 最多比较次数 n 平均比较次数 (n+1)/2 查找失败:最少比较次数 n 最多比较次数 n 平均比较次数 n • 优点：查找结构无特殊要求（线性结构均适 用）；算法简单； • 缺点：查找效率较低，不适于大表查找。 第 14 页
12折半查找(二分查找) Binary Search 上述按顺序査找表的查找算法简 单,但平均查找长度较大,不适用 于表长较大的查找结构。 若静态查找表为有序表,则查找 过程可以基于“折半”进行。 第15页
第 15 页 上述按顺序查找表的查找算法简 单，但平均查找长度较大，不适用 于表长较大的查找结构。 1.2 折半查找（二分查找） （Binary Search) 若静态查找表为有序表，则查找 过程可以基于“折半”进行