秒杀查找成功时的平均查找长度(ASL)计算

假设查找每 个记录的概率是相等的,n 为查找表中记录的个数

                                             ASL = 1/n * (每个查找元素深度之和)

 

OK,举个例子: 

秒杀查找成功时的平均查找长度(ASL)计算

深度为1的25的一个元素;

深度为2的10和30的两个个元素;

深度为3的2、15、28、35的四个元素;

深度为4的3、20、29、40的四个元素;

秒杀查找成功时的平均查找长度(ASL)计算

觉得????????吧?

再举个????

秒杀查找成功时的平均查找长度(ASL)计算

深度为1的4、12、49、13、32的五个元素;

深度为2的38、24、21的三个元素;

秒杀查找成功时的平均查找长度(ASL)计算

秒杀完毕~