有序表的索引顺序结构查找次数分析
@(算法学习)
为了提高查找效率,对65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。
A. 10
B.14
C. 20
D. 21
分析:明确一个概念:索引顺序结构就是分块结构。综合了顺序查找和折半查找的优点。
分析一下这种存储结构下查找的策略。分块查找的思路是:将查找表分为若干子块,块内元素可以无序,但是块之间有序,将每个块中的最值抽出来建立一个索引表。索引表存储的是每个块的最值和地址,关键字有序。因此可以对其进行折半查找加快速度。
再思考一般情况下折半查找平均查找长度。
折半查找树是一棵平衡树。
设为满的平衡树。高度为h,根结点高度是1.则每层最多结点是2h−12^{h-1}2h−1.
ASL=1n(1×1+2×2+...+h×2h−1)=1n((h−1)2h+1)ASL = \frac{1}{n}(1\times1+2\times2+...+h\times2^{h-1}) \\ = \frac{1}{n}\big((h-1)2^h+1\big) ASL=n1(1×1+2×2+...+h×2h−1)=n1((h−1)2h+1)
树高h=⌈log2(n+1)⌉h =\lceil log_2 (n+1)\rceilh=⌈log2(n+1)⌉
所以:
ASL≈log2(n+1)−1ASL \approx log_2(n+1)-1 ASL≈log2(n+1)−1
由这个公式可以推导上面的问题了。
将65025个关键字分组:65025=255\sqrt{ 65025 } = 25565025=255
即分为255块,每块255个元素时,将会有最小的平均查找次数。
总查找次数为:
ASL=log2(255+1)−1+log2(255+1)−1=14.ASL = log_2(255+1) - 1 + log_2(255+1) - 1 = 14. ASL=log2(255+1)−1+log2(255+1)−1=14.
.10 Update:
第一届PAT算法直播课培训班招募帖,欢迎点击查看详情、
END.