1. 梗概:
每次即任意给一个关键字, 该算法为查找该关键字, 需要进行的一定次数的比较, 当关键字给的次数比较多, 每次查找关键字的平均比较次数, 称为ASL
如果算法比较简单, 则可以直接推出平均查找长度 如果算法比较复杂, 则可用计算公式
2. 相关概念:
2.1. ASL中比较次数的定义:
并不是严格上的条件判断语句的次数, 而更像遍历不同记录的次数 如线性探测哈希表中, 每线性探测一次, 算作比较一次
2.2. 查找成功位置:
即查找关键字所在数据结构中的位置
2.3. 查找失败位置:
视具体算法而定
2.3.1. 哈希表中的查找失败位置:
即哈希函数算出来的位置
2.3.2. 折半查找的查找失败位置:
为mid指针最后停下的位置
3. 计算公式:
(n为该算法中记录表长, i为成功/失败位置 为i位置被查找的概率, 为算法共查找到i位置总共需要进行的比较次数) 一般来说, 查找的关键字是随机的, 所以任意位置为成功/失败位置的概率相等, 即 相等