、顺序表的查找(顺序查找) 顺序查找的缺点是平均查找长度较大,特别是当n很大 时,查找效率低。然而,它有很大的优点是:算法简单且 适应面广。 当査找不成功时的情形不忽视时,査找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 对于顺序查找,不论给定值key为何值,查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同,对每个记录的查找概率也相等, 则P ,此时顺序查找的平均查找长度为 2n AS ∑(m-i+1)+(n+1)=7(m+1) 4 北京邮电大学自动化学院北京邮电大学自动化学院 7 ⚫ 顺序查找的缺点是平均查找长度较大，特别是当n很大 时，查找效率低。然而，它有很大的优点是：算法简单且 适应面广。 n Pi 2 1 = ( 1) 4 3 ( 1) 2 1 ( 1) 2 1 1 ' =  − + + + = + = n i n n n ASL n i S S ⚫ 当查找不成功时的情形不忽视时，查找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 ⚫ 对于顺序查找，不论给定值key为何值，查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同，对每个记录的查找概率也相等， 则 ，此时顺序查找的平均查找长度为： 一、顺序表的查找（顺序查找）