| 查找方式 | $\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}}$ (最坏 $\mathrm{ASL}=n$) |
$O(\log_{2}n)$ |
哈希查找 の ASL
-
哈希查找 ASL，散列函数影响不大，主要影响在于冲突处理
-
哈希查找 ASL 依赖装填因子 $\alpha$ := $$\alpha=\frac{表中填入项数}{哈希表容量}$$
| 哈希查找 | $\mathrm{ASL}_{成功}$ | $\mathrm{ASL}_{失败}$ |
|---|---|---|
| 线性探测 | $\frac{1}{2}(1+\frac{1}{1-\alpha})$ | $\frac{1}{2}(1+\frac{1}{(1-\alpha)^{2}})$ |
| 二次探测/伪随机探测/二哈希 | $\frac{1}{\alpha}\ln\frac{1}{1-a}$ | $\frac{1}{1-\alpha}$ |
| 拉链法 | $1+\frac{\alpha}{2}$ | $\alpha+e^{-\alpha}$ |