请教一道ds题: 求12个结点顺序表折半搜索的ASL

beyondyuefei · 发表于 07-9-14 18:45:31

我原来是直接带公式O(log2^n) ,那么结果就是O(log2^12),结果答案确是 37/12.
我又看了书上这部分内容,后来我用 ASL=1/n(1x1+2x2+...)这个公式算出来了,确实为37/12. 是不是先算高度h,然后就用这个公式算,如果不是满2叉树,则最后一层结点数另算.是这样做的么? 我原来的做法错误是否因为O(log2^n)这个只是它的大O表示法而已?

alpha2008 · 发表于 07-9-14 22:19:50

构造12节点的二叉判定树,第一层是1个节点,第二层是2个节点,第三层是4个节点,第四层是5个节点,因此查找成功时的平均查找长度ASL是(1*1+2*2+3*4+4*5)/12=37/12,即每层的节点个数乘以该层的所在的层数,再除以总的节点数目,而O(log2^n) 只是用来估算的,用于定性的分析.

beyondyuefei · 发表于 07-9-14 22:24:59

谢谢,证实了我的想法

pltl1985 · 发表于 07-9-15 21:04:12

============================================
查找成功时的平均查找长度ASL即每层的节点个数乘以该层的所在的层数,
再除以总的节点数目,用于定量分析；
而O(log2^n) 只是用来估算的,用于定性的分析.
============================================

fcy19831021 · 发表于 07-9-16 13:09:39

楼上的回答很正确,支持!

		自动登录	找回密码
密码			注册

请教一道ds题: 求12个结点顺序表折半搜索的ASL

alpha2008

回复 #2 alpha2008 的帖子