参考提示:请阅读教材1第9章、电子学材-查找、多媒体材料的顺序查找和二分查找。
模拟场景:在查找过程中,给定值与关键字的平均比较次数的期望值称为平均查找长度,通常用ASL表示。在每一个记录的查找概率相等的情况下,平均查找长度ASL的计算公式如下:
ASL = åCi / n ,0 £ i £ n-1.
其中,n为查找表中记录的个数,也称为表长;Ci为查找第个记录时关键字值与给定值比较的次数。平均查找长度是衡量一个查找算法优劣的标准。
提问:请根据上述定义计算查找成功时顺序查找和二分查找的平均查找长度?哪个查找算法较好?并请解释原因?
点点赞赏,手留余香
给TA打赏