请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*
来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/05/21 21:13:48
请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减一,但是概率为什么没有变,我知道如果概率每次也增大的话最终结果会是n,但是ASL为什么需要这样多次相加得出呢?这似乎和抽奖的问题一样,放回与不放回的概率是不一样的,为什么却说先抽奖和后抽奖的概率一样呢?这个ASL算法似乎是不放回吧,而且也只是一次比较!
是和概率有关,但是与放回与不放回的概率不同.查找第几个数,是随机的,所以查找的次数也是随机的,即查找次数是随机变量,随机变量的平均值就是随机变量的数学期望,是随机变量值与取这个值的概率的乘积之和.
一般来说,顺序查找采用由后向前逐个比较的方法(由前向后雷同),n个元素查找第1个需要查找n次,查找第2个需要查找n-1次,……,查找第n个需要查找1次,所以
ASL=n*p1+(n-1)*p2+…+2*pn-1+pn
这里p1=P(X=1),……,pn=P(X=n).是从n个元素中,查找第几个的概率.要查找第几个,都是等概的,不变的,所以都是1/n,因此
ASL=n*p1+(n-1)*p2+…+2*pn-1+pn =1/n(1+2+3+……+n)=(n+1)/2.
关键在搞清pi的涵义,它是表示从n个元素中,查找第i个的概率,总体元素个数始终是n,所以概率是不变的,也可以说相当于(不等同于)放回的情况;如果是每次查找一个元素,后一次在前一次剩余的元素中查找,pi表示第i次找到的概率,总体元素个数始终改变,概率就是变动的了,相当于(不等同于)不放回的情况.但是,这里是前者.
一般来说,顺序查找采用由后向前逐个比较的方法(由前向后雷同),n个元素查找第1个需要查找n次,查找第2个需要查找n-1次,……,查找第n个需要查找1次,所以
ASL=n*p1+(n-1)*p2+…+2*pn-1+pn
这里p1=P(X=1),……,pn=P(X=n).是从n个元素中,查找第几个的概率.要查找第几个,都是等概的,不变的,所以都是1/n,因此
ASL=n*p1+(n-1)*p2+…+2*pn-1+pn =1/n(1+2+3+……+n)=(n+1)/2.
关键在搞清pi的涵义,它是表示从n个元素中,查找第i个的概率,总体元素个数始终是n,所以概率是不变的,也可以说相当于(不等同于)放回的情况;如果是每次查找一个元素,后一次在前一次剩余的元素中查找,pi表示第i次找到的概率,总体元素个数始终改变,概率就是变动的了,相当于(不等同于)不放回的情况.但是,这里是前者.
在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时平均查找长度为多少
数据结构题目:才用折半查找算法在长度为12的有序表中查找一个元素时,查找成功的平均查找长度为多少?...
在一个长度为n顺序线性表中顺序查找值为x的元素时,查找的平均长度为
顺序表长度为n的折半查找算法的平均查找长度
关于数据结构二分法查找成功的平均查找长度和失败的查找长度
数据结构有一个长度为12的有序表,按二分查找法对该表进行查找,在表内个元素等概率情况下,查找成功所需
关于数据结构 查找定一个集合,查找元素是否在集合中出现.输入每个测试用例由多行组成,第一行是两个整数n和m,两个数范围在
算平均查找长度长度为12的按关键字有序的查找表采用顺序组织方式,若用二分法查找,则在等概率情况下,查找不成功的平均查找长
关于哈希表查找不成功时的平均查找长度
有一个长度为12的有序表,按折半查找法对表进行查找,在表内各元素等概率的情况下查找成功所需的平均比较次
计算各种查找方法在等概率情况下查找成功时的平均查找长度
数据结构折半查找的二叉查找树的问题