作业帮请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/10 01:25:29
请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减
请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减一,但是概率为什么没有变,我知道如果概率每次也增大的话最终结果会是n,但是ASL为什么需要这样多次相加得出呢?这似乎和抽奖的问题一样,放回与不放回的概率是不一样的,为什么却说先抽奖和后抽奖的概率一样呢?这个ASL算法似乎是不放回吧,而且也只是一次比较!
请教关于数据结构的一个问题!在查找这一张中有一个概念叫做平均查找长度,以顺序查找为例,求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算?每一次查找后总的顶点数目会减一,所以n的数目会减
是和概率有关,但是与放回与不放回的概率不同.查找第几个数,是随机的,所以查找的次数也是随机的,即查找次数是随机变量,随机变量的平均值就是随机变量的数学期望,是随机变量值与取这个值的概率的乘积之和.
一般来说,顺序查找采用由后向前逐个比较的方法（由前向后雷同）,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次找到的概率,总体元素个数始终改变,概率就是变动的了,相当于（不等同于）不放回的情况.但是,这里是前者.