更新时间:2024-05-21 11:50
平均查找长度(Average Search Length,简称ASL)是一个专用术语。
含义
为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的数学期望值称为查找算法在查找成功时的平均查找长度,ASL成功。
对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中:Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数。
在查找表中查找不到待查元素,但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度,不成功。