顺序检索性能分析(续) 平均检索长度 假设检索成功的概率为p,检索失败的概率为q=(1-p), 则平均检索长度为 n+1 ASL= p +q·(n+1) 2 n+1 +(1-P)(n+1) 2 (n+1)(1-P/2) (n+1)/2<ASL<(n+1) 优缺点 优点:插入元素可以直接加在表尾⊙(1) 缺点:检索时间太长e(n) 北京大学信息学院 版权所有,转载或翻印必究 Page 15北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 顺序检索性能分析（续） ◼ 平均检索长度 假设检索成功的概率为p，检索失败的概率为q=(1-p)， 则平均检索长度为 ◼ （n+1)/2 < ASL < (n+1) ◼ 优缺点 优点：插入元素可以直接加在表尾Θ(1) 缺点：检索时间太长Θ(n) 1 ASL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p q n n p p n n p + =  +  + + =  + − + = + −