平均检索长度(ASL) 关键码的比较:检索运算的主要操作 平均检索长度( Average Search Length) 检索过程中对关键码的平均比较次数 衡量检索算法优劣的时间标准 ASl PC P为检索第个元素的概率 ci为找到第i个元素所需的关键码值与 给定值的比较次数 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 6
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 平均检索长度（ASL） 关键码的比较：检索运算的主要操作 平均检索长度(Average Search Length) 检索过程中对关键码的平均比较次数 衡量检索算法优劣的时间标准 1 n i i i A SL P C = = ∑ Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与 给定值的比较次数
平均检索长度的例子 假设线性表为(abc)检索a、 b、c的概率分别为04、01、05 n顺序检索算法的平均检索长度为 04×1+01×2+05×3=21 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 平均检索长度的例子 假设线性表为（a, b, c）检索a、 b、c的概率分别为0.4、0.1、0.5 顺序检索算法的平均检索长度为 0.4×1+0.1×2+0.5×3 = 2.1 即平均需要2.1次给定值与表中关键 码值的比较才能找到待查元素
检索算法评估的几个问题 衡量一个检索算法还需要考虑 算法所需的存储量 算法的复杂性 ■■■ 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 8
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 检索算法评估的几个问题 衡量一个检索算法还需要考虑 算法所需的存储量 算法的复杂性
9.1基于线性表的检索 9.1.1顺序检索 Q9.1.2二分检索 9.1.3分块检索 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 9
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 9.1 基于线性表的检索 9.1.1 顺序检索 9.1.2 二分检索 9.1.3 分块检索
9.1.1顺序检索 针对线性表里的所有记录,逐个进 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 等,则检索成功; 否则检索失败(找遍了仍找不到)。 ■存储:可以顺序、链接 排序要求:无 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 10
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 9.1.1 顺序检索 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 若某个记录的关键码和给定值比较相 等，则检索成功 ； 否则检索失败(找遍了仍找不到)。 存储：可以顺序、链接 排序要求：无