长度为n(900)的表分成均等的b(25)个子表,则每个子表的长度为s,b=n/s(900/25=36)。
顺序查找时成功的平均查找长度为:
(b+s)/2+1=(25+36)/2+1=44
例如:
每块最佳长度为:根号625= 25,即每块25个结点,一共分为25块,此时平均查找长度=2((25+1)/2)= 26
扩展资料:
分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序。当节点很多且块数很大时,对索引表可以采用折半查找,这样能够进一步提高查找的速度。
分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时,只需将该节点调整到所在的块即可。在空间复杂性上,分块查找的主要代价是增加了一个辅助数组。
参考资料来源:百度百科-分块查找
怎么做?
本回答被提问者采纳