| 查找方式 | $\mathrm{ASL}_{成功}$ | $\mathrm{ASL}_{失败}$ | 时间复杂度 |
|---|---|---|---|
| 无序线性表 顺序查找 | $\frac{n+1}{2}$ | $n+1$ | $O(n)$ |
| 有序线性表 顺序查找 | $\frac{n+1}{2}$ | $\frac{1+2+\dots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$ | $O(n)$ |
| 折半查找 | $\frac{1}{n}(1\times1+2\times2+\dots+h\times2^{h-1})$ $=\frac{n+1}{n}\log_{2}(n+1)-1$ $\approx \log_{2}(n+1)-1$ |
$\sum h\times \mathrm{num}_{h}$ | $O(\log_{2}n)$ |
| $b\times s$ 分块查找 | $\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^{2}+2s+n}{2s}$ | $O(\sqrt{ n })$ | |
| 二叉排序树 | $\frac{\sum \mathrm{node}{i}\times h{i}}{\sum\mathrm{node}_{i}}$ | $O(\log_{2}n)$ |