顺序检索性能分析 检索成功 假设检索每个关键码是等概率的,Pi=1/n ∑Pi·(n-i)=∑(n-i) i=0 i=0 ÷h+l 2 检索失败 假设检索失败时都需要比较n+1次(设置了一个监视 北京大学信息学院 版权所有,转载或翻印必究 Page 14北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 顺序检索性能分析 ◼ 检索成功 假设检索每个关键码是等概率的，Pi = 1/n ◼ 检索失败 假设检索失败时都需要比较n+1次（设置了一个监视 哨） Pi n i i n n n i i n i n i n ·( − ) ( ) = −  = − = −  = = + =  0 1 1 0 1 1 2 1