Question

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

请教关于数据结构的一个问题！在查找这一张中有一个概念叫做平均查找长度，以顺序查找为例，求法ASL=n*p1+(n-1)*p2+…+2*pn-1+pn,为什么这么算？每一次查找后总的顶点数目会减一，所以n的数目会减一，但是概率为什么没有变，我知道如果概率每次也增大的话最终结果会是n，但是ASL为什么需要这样多次相加得出呢？这似乎和抽奖的问题一样，放回与不放回的概率是不一样的，为什么却说先抽奖和后抽奖的概率一样呢？这个ASL算法似乎是不放回吧，而且也只是一次比较！

Answer 1

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

Answer 2

你是不会给财富值得

追问

什么？？？

……简直无聊透顶