分块查找平均查找长度计算公式是什么

分块查找平均查找长度计算公式是什么
顺序查找和折半查找标明每个未知量的含义谢了

完住 1年前已收到1个回答举报

共回答了23个问题采纳率：95.7% 举报

设关键字个数为n,在各关键字等概率查找的前提下,
1、顺序查找的平均查找长度ASL=(n+1)/2,
2、在n趋于无穷大时,折半查找的ASL=((n+1)log2(n+1))/n - 1,当n大于50时,ASL约等于log2(n+1)-1
3、设分块查找中将长为 n 的表分成均等的 b 个块,每块 s 个元素,则 b = (n / s)上取整,如果索引表中采用顺序查找,则ASL=(b+1)/2+(s+1)/2；如果索引表中采用折半查找,则ASL=(s+1)/2+log2(b+1)-1

1年前追问

完住举报

144个记录的文件，分块查找法，折半查找确定块，每块长度8，则平均查找长度是多少帮做一下，我算的结果和答案不一样

举报火箭粑粑

差别不会很大吧，因为那个ASL=(s+1)/2+log2(b+1)-1中的折半查找用的是理论值 144条记录，每块8条，则索引项为144/8=18项，块内查找是(8+1)/2= 4.5，索引中用折半查找18项的ASL准确值是(1*1+2*2+4*3+8*4+3*5)/18 = 64/18约等于3.5 所以ASL约为3.5+4.5 = 8

完住举报

答案不是那个啊答案是14难道是答案错了

举报火箭粑粑

答案是14，那就是这个索引表中采用顺序查找而不是折半查找，则ASL=(b+1)/2+(s+1)/2=(8+1)/2+(18+1)/2=14 如果确实题目是如此：分块查找法，折半查找确定块，那就是答案弄错了

可能相似的问题

你能帮帮他们吗

精彩回答