平均查找长度 （ASL）

不知道为什么最近喜欢写一些理论性并且与算法无关的知识，可能是因为初赛题刷多了且知识点不难，所以对这些新鲜的知识点有好感，那今天就写一篇ASL的文章，诸君就当小说看着玩吧 ?

平均查找长度

是为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。(Average Search Length，ASL)

百科的概念有些难懂，这里的长度其实不是一个具体的长度，而是衡量一个算法时间性能的数值，在许多算法中我们都需要查找某个值，或者是对某个值做更改，既然要做更改那就必须先找到你所要查找的数，再将其更改为自己所需要的数，可见查找这一行为的普遍。
而当查找的时候，花费的时间大多在值与值的比较中，比如，判断相等要写if，判断dp的容积有没有越界，也要写if，所以把平均需要/和待查找值比较的/关键字次数/称为平均查找长度。（为读者断句，方便理解）

ASL既然与比较次数，也就是查找次数有关，那么其定义如下式：
$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

其中n为查找表中元素个数，Pi为查找到第i个元素的概率，通常设每个元素查找概率相同，即Pi=1/n，Ci是找到第i个元素的所需要的比较次数。
注意：ASL只能用于静态查找表中顺序表的查找，如果你的一个表是动态的，即表中的数值时时刻刻都在变动，其出现的概率也会变动，就会影响$P_i\times C_i$，那么自然就会影响到Sigma的取值。

上文提到，ASL是衡量一个算法时间性能的数值，而根据定义理解，和给定值进行比较的关键字个数的期望值，若你查找某一个数的期望大，即有可能经历的查找次数多，时间复杂度自然就高，所以一个算法的ASL越大，说明时间性能差，反之，时间性能好。

顺序查找(Sequence Search)

在顺序查找表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci在于这个元素在查找表中的位置，如第0号元素直接赋值，第一号元素比较1次…第n号元素要比较n次。所以Ci=i。所以
$$AS{L}_{成功}=\sum _{i=1}^n{P}_i{C}_i=\frac{1}{n}\cdot \sum _{i=1}^{n}i=\frac{1}{n}\cdot \frac{n\cdot (n+1)}{2}=\frac{n+1}{2}$$

可以看出，顺序查找方法查找成功的平均 比较次数约为表长的一半。当待查找元素不在查找表中时，也就是扫描整个表都没有找到，即比较了n次，查找失败,即
$AS{L}_{不成功}=n$
eg：对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ).(NOIP2014)
/2
B.(n+1)/2
C.(n-1)/2
/4

分析：因为是单链表,所以只能从链头开始向后遍历，即$C_i=i$同时$P_i=\frac{1}{n}$所以直接代入公式就得到答案$\frac{n+1}{2}$