88问答网
所有问题
折半查找时ASL=(n+1/n)log(2)(n+1)-1这个是怎么的出来的
如题所述
举报该问题
其他回答
第1个回答 2022-06-30
如果你知道树这种数据结构的话就知道了，不好意思这里没有办法跟你讲。因为讲解这个最好是有图形来给你讲解，你可以去查查数据结构与算法的书，里面就有了。log(2)(n+1)这个是树的高度，而n代表树的结点数。
通常有出现log(2)这样的形式，都会跟树有关系。
相似回答
折半查找
平均查找长度如何计算?
答：
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+...
二
分
查找
法平均查找长度公式
答：
这个公式是
ASL = (log2(n+1) - 1)
* (n+1) / n。n值较大时，(n+1)/n可以忽略。二分查找比顺序查找的效率要高，但它要求查找表进行顺序存储并且按关键字有序排列，所以它适用于表不易变动而且经常进行查找的情况。二分查找也称为
折半查找
，其基本思想是：先令查找表中间位置记录的关键字...
顺序
+折半+
分块
查找+
B树和(B
+)
树
答：
ASL
成功
=(n+1
)/2 ASL失败=n+1 2.有序表的顺序查找 查找判定树
（二
分查找） 仅适用于有序的顺序表 判定树 ASL成功=
log2(n+1)-1
（索引顺序查找） 吸取了顺序查找和
折半查找
各自的优点，即有动态结构，又适于快速查找。 基本思想 ：将查找表分为若干子块，块内无序，...
折半查找
不成功的
ASL
计算公式
答：
n->无穷大时的均值为
log2(n+1)
对于长度为18的顺序存储的有序表,若采用
折半查找
,则比较4次就能查找的...
答：
折半查找的
平均查找长度公式为：
ASL=
{[
(n+1)
/n]*
log2
^(n+1)}-1。折半查找原码是：if (key==r[mid]) return mid;else if(key>r[mid]) low = mid+1;else(key<r[mid]) high = mid-
1;
第一次和37比较，第
二
次和12比较，第三次和20比较，第四次和26比较，所以是4次。
折半查找
判定树特点
答：
2、长度为n的
折半查找
判定树的构造方法。当n=0时，折半查找判定树为空；当n＞0时，折半查找判定树的根结点是有序表中序号为mid
=(n+1)
/
2的
记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。
有
一
个长度为12的有序表,按
折半查找
法对表进行查找,在表内各元素等概 ...
答：
需要
查找1
次的排序为：第 6 需要
查找2
次的排序为：第 3,9 需要查找3次的排序为：第 1,4,7,10 需要查找4次的排序为：第 2,5,8,11,12 平均查找长度：
（1
*
1+2
*
2+
3*4+4*4）/12 = 37/12
什么是
折半查找
法
答：
折半查找是一
种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，
折半查找的
先决条件是查找表中的数据元素必须有序。算法步骤描述：step
1
首先确定整个查找区间的中间位置mid = （ left + right ）/ 2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在...
大家正在搜
折半查找查找失败时的平均查找长度
求折半查找成功时的平均查找长度
折半查找ASL怎样算
折半查找的ASL计算
折半查找当有序表为偶数个时
二分查找和折半查找
什么是折半查找法
折半查找的时间复杂度
对线性表进行折半查找时