查找

顺序表的查找

顺序查找

平均查找长度

查找成功：

$$ASL=\sum _{i=1}^n\frac{1}{n}i=\frac{n+1}{2}$$

查找失败：

$$ASL=n$$

二分查找

可以看成在一个二叉树上找一个节点，这里使用满二叉树作为典型：对于每次查找，查找次数为层数

查找成功：

$$ASL=\frac{1}{n}\sum _{h=1}^{{\log }_2(n+1)}{2}^{h-1}\cdot h=\frac{n+1}{n}{\log }_2(n+1)-1\approx {\log }_2(n+1)-1$$

查找失败：

$$ASL={\log }_2(n+1)$$

索引表查找

索引表

先二分 + 后顺序：s 为分块大小

查找成功：

$$ASL\approx {\log }_2\left(\frac{n}{s}+1\right)-1+\frac{s+1}{2}={\log }_2\left(\frac{n}{s}+1\right)+\frac{s-1}{2}$$

查找失败：

$$ASL={\log }_2\left(\frac{n}{s}+1\right)+s$$

哈希表查找

哈希表

哈希表查找：按照插入的算法查找，直到为空停止。同时要提供一个查找的冲突次数来为扩容判断

哈希表的平均查找长度是装填因子的函数，而不是数据规模的函数

查找成功平均长度

线性探测再散列：

$$ASL\approx \frac{1}{2}\left(1+\frac{1}{1-\alpha }\right)$$

伪随机、二次探测再散列和再哈希：

$$ASL\approx \frac{1}{\alpha }\ln (1-\alpha )$$

链地址法：

$$ASL\approx 1+\frac{\alpha }{2}$$

不成功平均查找长度