请教关于数据结构的一个问题！在查找这一张中有一个概念叫做平均查找长度，以顺序查找为例，求法ASL=

发布网友发布时间：2022-05-11 05:36

共2个回答

热心网友时间：2024-02-09 21:11

　　是和概率有关，但是与放回与不放回的概率不同。查找第几个数，是随机的，所以查找的次数也是随机的，即查找次数是随机变量，随机变量的平均值就是随机变量的数学期望，是随机变量值与取这个值的概率的乘积之和。
　　一般来说，顺序查找采用由后向前逐个比较的方法（由前向后雷同），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次找到的概率，总体元素个数始终改变，概率就是变动的了，相当于（不等同于）不放回的情况。但是，这里是前者。

热心网友时间：2024-02-09 21:11

你是不会给财富值得追问什么？？？

……简直无聊透顶