对含有3600个元素的顺序表进行分块查找,若索引表和方块均采用顺序查找方法,最理想的块长是______。
A. 1800
B. 60
C. 1200
D. log23600
我的解题思路:(希望对你有所帮助~~)
已知索引表和方块都采用顺序查找的方式,我们设方块的块长为L,那么索引表的元素个数为3600/L。
(对于顺序查找,元素的平均查找长度为各个元素的查找长度之和除以元素个数,即(1+2+...+n)/n ---> (n/2)*(n+1) ) / n ---> (n+1) / 2 )
(这是等差数列的前n项和公式,至于不懂为什么要这么算我就不多赘述了,动动你聪明的脑袋瓜子好好想想就行)
准备工作已经完成,下面我们开始计算:
理想的块长无非就是得到更好的查找效率也就是更少的平均查找长度,这样查找的时间就更少。
对索引表的平均查找长度为:( (3600 / L) + 1) / 2
对方块内的平均查找长度为:( L + 1) / 2
把它俩相加(不是相乘嗷,不明白的自己好好想想),得到总的平均查找长度为1/2 * (3600 / L + 1 + L + 1)。
我们可以很容易看出3600 / L + L >= 2 * sqrt( ( 3600 / L ) * L ) = 120【基本不等式】
当且仅当3600 / L = L时等式成立,即L^2 = 3600 ---> L = 60(-60舍去)。
Djiangxu 回复 Djiangxu: 然后以后看到这种题目就可以直接对元素个数开方啦。(弄懂了原理之后是这样的嘿嘿,有公式做题就是快啊)
分块查找的最佳块长:s^2=n
开方
B
用户登录可进行刷题及查看答案
登录后提交答案