2、顺序查找（续） 算法评估 平均查找长度 对于含n个数据元素的查找表，查找成功时的平均查找长度为： ASL=∑PC i=l 其中：P为查找第I个元素的概率，C为查到第I个元素时进行比较的次数 假设查找表中每个数据的查找概率相同，即P,=1/n,查找第I个元素 的比较次数为C=I,则顺序查找算法成功查找的平均查找长度为： ASLg=∑PC,=∑（日×）=n+1) i=1 i=1 对结点的逻辑次序（不必有序）和存储结构（顺序、链表均可）无要求 ;当序列中的记录“基本有序”或N值较小时，是较好的算法。但平 均查找时间长。 电子科技大学刘民岷 查找算法 5电子科技大学 刘民岷 查找算法 5 • 算法评估 ➢ 平均查找长度 对于含n个数据元素的查找表，查找成功时的平均查找长度为： 其中：Pi为查找第I个元素的概率，Ci为查到第I个元素时进行比较的次数 ➢ 假设查找表中每个数据的查找概率相同，即Pi ＝1/n，查找第I个元素 的比较次数为Ci ＝I，则顺序查找算法成功查找的平均查找长度为： ➢ 对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求 ；当序列中的记录“基本有序”或N值较小时，是较好的算法。但平 均查找时间长。 = = n i ASL Pi Ci 1   = = = =  = + n i n n i S q i i ASL PC i n 1 2 1 1 1 ( ) ( 1)