顺序查找的平均查找长度 设查找第i个元素的概率为P,查找到第i个元素 所需比较次数为c,则查找成功的平均查找长度: ASL ∑P;c,(∑p1=1) i=1 在顺序查找情形,c1=ni+1,i=1,…,n,因此 ASL ∑P1:(n-i+1) 在等概率情形,P;=1/n,i=0,1,…,n-1 ASL (n-i+1) ln(n+1)n+1 2       n i i n i ASL succ pi ci p 1 . ( 1 ) 1 ( ) 1      1  ASL p i n i succ i n . ( )  ( )          n i succ n n n n i n ASL 1 2 1 2 1 1 1 1 n