查找操作的性能分析-软考在线

查找操作的性能分析



考试要求：掌握

知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 > 常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法 > 查找的基本概念

通常以"其关键字和给定值进行过比较的记录个数的平均值"作为衡量查找算法好坏的依据。

平均查找长度：为确定记录在查找表中的位置，须与给定关键字值进行比较的次数的数学期望称为查找算法在查找成功时的平均查找长度。

对于含有n个记录的表，平均查找长度ASL定义为

式中，p_i为对表中第i个记录进行查找的概率，且

。一般情况下，均认为查找每个记录的概率是相等的，即p_i=1/n。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5