常见的平均查找长度总结

// 部分图片源自网络****

1. 平均查找长度(ASL)

常见的平均查找长度总结

  1. pi 是查找到某个元素的概率(probability)
  2. ci 是查找到这个元素时已经比较的次数,如,查找在 10 个数中查找第 5 个数,其比较的次数是多少(包括和第 5 个数比较的次数)

2. 顺序查找的 ASL

常见的平均查找长度总结

2. 折半查找 ASL

折半查找的 ASL 利用二叉判定树计算
常见的平均查找长度总结
NOTE:
每个结点的比较次数之和,即该结点所在的层次数
空指针处比较次数之和,就是该空指针的双亲结点所在的层次

3. 散列表中地址链接法的 ASL

ASL_成功 = 每个元素被访问(查找)的次数
ASL_失败 = 每个地址被访问(查找)的次数
常见的平均查找长度总结
常见的平均查找长度总结

常见的平均查找长度总结