秒杀查找成功时的平均查找长度(ASL)计算
假设查找每 个记录的概率是相等的,n 为查找表中记录的个数
ASL = 1/n * (每个查找元素深度之和)
OK,举个例子:
深度为1的25的一个元素;
深度为2的10和30的两个个元素;
深度为3的2、15、28、35的四个元素;
深度为4的3、20、29、40的四个元素;
觉得????????吧?
再举个????
深度为1的4、12、49、13、32的五个元素;
深度为2的38、24、21的三个元素;
秒杀完毕~
假设查找每 个记录的概率是相等的,n 为查找表中记录的个数
ASL = 1/n * (每个查找元素深度之和)
OK,举个例子:
深度为1的25的一个元素;
深度为2的10和30的两个个元素;
深度为3的2、15、28、35的四个元素;
深度为4的3、20、29、40的四个元素;
觉得????????吧?
再举个????
深度为1的4、12、49、13、32的五个元素;
深度为2的38、24、21的三个元素;
秒杀完毕~