CLRS 习题解析：Problem 11-1 —— 开放寻址散列表最长探测序列的概率界

文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载导读本篇基于 docs/Chap11/Problems/11-1.md 的原始题面系统讲解《算法导论》Introduction to Algorithms, Third Edition第 11 章 Problem 11-1 的完整推导。该题研究在均匀散列uniform hashing假设下开放寻址散列表逐次插入 n 个元素时所需探测次数probe的尾概率上界并最终证明全部 n 次插入中最长探测序列的期望长度为 O(lg n)。读完本文你将掌握尾概率链式放缩、联合界union bound与尾和公式tail-sum formula三种典型的概率分析手法并理解它们如何组合出散列表最坏情形下的期望行为。问题定位与背景知识开放寻址与探测序列开放寻址open addressing是一种将所有元素直接存放在散列表槽位中的冲突解决方式当插入一个键 k 时依次考察探测序列$$h(k, 0), h(k, 1), \ldots, h(k, m-1)$$直到找到一个空槽。与之相对的是链地址法chaining后者在 11.2.md 中有大量配套习题如 11.2-2 给出了h(k) k mod 9的分链示例11.2-6 讨论如何在已知最长链长度 L 时均匀随机抽取一个键。本问题聚焦开放寻址其核心随机量是单次插入所需的探测次数X_i 与全程最长探测序列X max_{1 ≤ i ≤ n} X_i。均匀散列假设与装载因子题目要求的推导建立在均匀散列假设之上每个键的探测序列等可能地是 m 个槽位的任意一种排列共 m! 种。因此在探测过程中每次新探测到的槽位是尚未探测过的槽位中的均匀随机一个这保证了条件概率的链式放缩是合法的。记装载因子$$\alpha \frac{n}{m}$$本问题的关键前提是n ≤ m/2即装载因子不超过 1/2。这个前提保证了表远未填满探测很少会走遍整张表从而可以给出指数衰减的尾概率。前置理论期望探测次数上界定理 11.6 与 11.8书中第 11.4 节的两个经典上界在本问题的背景中反复出现仓库配套习题 11.4-3 与 11.4-5 即直接引用这两个定理定理 11.6不成功查找的期望探测次数均匀散列下不成功查找的期望探测次数至多为$$\frac{1}{1 - \alpha}$$定理 11.8成功查找的期望探测次数均匀散列下成功查找的期望探测次数至多为$$\frac{1}{\alpha} \ln \frac{1}{1 - \alpha}$$11.4-3 代入 α 3/4 与 α 7/8 分别得到不成功查找期望 4 次与 8 次探测成功查找期望约 1.848 次与约 2.377 次探测。而 11.4-5 利用这两个上界求解方程 1/(1-α) 2·(1/α)ln(1/(1-α))得到 α ≈ 0.71533。这些结果关注的是平均行为而 Problem 11-1 关注的是更精细的尾部行为与最坏情形二者互为补充。原题重述仓库原文完整保留仓库文件 docs/Chap11/Problems/11-1.md 给出了完整题面其解答部分标注为(Removed)该仓库对部分题目刻意删去了解答。题面如下Suppose that we use an open-addressed hash table of size $m$ to store $n \le m / 2$ items.a.Assuming uniform hashing, show that for $i 1, 2, \ldots, n$, the probability is at most $2^{-k}$ that the $i$th insertion requires strictly more than $k$ probes.b.Show that for $i 1, 2, \ldots, n$, the probability is $O(1 / n^2)$ that the $i$th insertion requires more than $2\lg n$ probes.Let the random variable $X_i$ denote the number of probes required by the $i$th insertion. You have shown in part (b) that $\Pr{X_i 2\lg n} O(1 / n^2)$. Let the random variable $X \max_{1 \le i \le n} X_i$ denote the maximum number of probes required by any of the $n$ insertions.c.Show that $\Pr{X 2\lg n} O(1 / n)$.d.Show that the expected length $\text E[X]$ of the longest probe sequence is $O(\lg n)$.四问层层递进先证明单次插入的指数尾概率a再取 $k 2\lg n$ 得到多项式尾概率b随后用联合界把所有 n 次插入合并为全程最长探测序列的尾概率c最后借助尾和公式把概率界翻译成期望界d。下文逐问给出完整推导。逐问推导与证明a. 第 i 次插入需要超过 k 次探测的概率至多 $2^{-k}$在第 i 次插入发生时表中已经存有 i - 1 个元素。由于均匀散列第 i 次插入的第 1 次探测命中有元素槽位的概率为$$\frac{i - 1}{m} \le \frac{n - 1}{m} \le \frac{n}{m} \le \frac{1}{2}$$若前 j 次探测全部命中已占用槽位则第 j 1 次探测命中有元素槽位的条件概率为$$\frac{i - 1 - j}{m - j} \le \frac{i - 1}{m} \le \frac{1}{2}$$分子分母同步减去已探测过的 j 个槽位比值不会变大。由概率的链式法则第 i 次插入需要严格超过 k 次探测等价于前 k 次探测全部命中已占用槽位因此$$\Pr{X_i k} \le \left(\frac{1}{2}\right)^k 2^{-k}$$这里有两个值得注意的细节条件概率放缩到 (i-1)/m ≤ n/m ≤ 1/2 时结论与 i 的具体取值无关因此该上界对 i 1, 2, ..., n 一致成立放缩只用到了 $n \le m / 2$它保证了每步命中的条件概率都不超过 1/2从而形成指数衰减。b. 超过 $2\lg n$ 次探测的概率为 $O(1 / n^2)$直接取 a 问的结论令 $k 2\lg n$$$\Pr{X_i 2\lg n} \le 2^{-2\lg n} \left(2^{\lg n}\right)^{-2} n^{-2}$$即$$\Pr{X_i 2\lg n} O!\left(\frac{1}{n^2}\right)$$这一结果把指数尾界翻译成了关于元素个数 n 的平方倒数为 c 问的联合界提供了基础。c. 最长探测序列超过 $2\lg n$ 的概率为 $O(1 / n)$定义全程最长探测序列 $X \max_{1 \le i \le n} X_i$。事件 ${X 2\lg n}$ 等价于存在某次插入 i 使得 $X_i 2\lg n$即$${X 2\lg n} \bigcup_{i1}^{n} {X_i 2\lg n}$$由联合界union bound即 $\Pr{\cup_i A_i} \le \sum_i \Pr{A_i}$并结合 b 问对每个 i 一致成立的上界$$\Pr{X 2\lg n} \le \sum_{i1}^{n} \Pr{X_i 2\lg n} \le n \cdot O!\left(\frac{1}{n^2}\right) O!\left(\frac{1}{n}\right)$$这说明尽管单次插入出现长探测序列的概率只有 $O(1/n^2)$但由于要同时管理 n 次插入全程最长的探测序列突破 $2\lg n$ 的概率被放大到 $O(1/n)$。这一概率仍然趋近于 0只是衰减得慢了一个数量级。d. 最长探测序列的期望长度为 $O(\lg n)$对非负整值随机变量 X期望可以由尾和公式tail-sum formula表示$$\text E[X] \sum_{k 0}^{\infty} \Pr{X k}$$将求和按阈值 $k_0 2\lg n$ 分为两段第一段0 ≤ k 2 lg n概率不超过 1因此这一段至多贡献 $2\lg n$。第二段k ≥ 2 lg n对任意 $k \ge 2\lg n$结合 a 问与联合界$$\Pr{X k} \le n \cdot 2^{-k}$$于是第二段的上界为等比级数$$\sum_{k 2\lg n}^{\infty} n \cdot 2^{-k} n \cdot \frac{2^{-2\lg n}}{1 - 1/2} n \cdot 2^{1 - 2\lg n} \frac{2n}{n^2} \frac{2}{n}$$综合两段$$\text E[X] \le 2\lg n \frac{2}{n} O(\lg n)$$结论在 $n \le m/2$即装载因子至多 1/2与均匀散列的假设下开放寻址散列表 n 次插入中最长探测序列的期望长度为 $O(\lg n)$。这个结果的证明脉络值得单独强调——它展示了概率分析中三个基本工具的接力步骤工具作用a → b指数尾界 取 k 2 lg n得到单次插入的多项式尾概率b → c联合界union bound把 n 次插入合并为全程最大值c → d尾和公式 E[X] Σ Pr{X k}把尾概率翻译为期望上界边界条件讨论为什么要求 $n \le m / 2$a 问的每一步条件概率都放缩到 (i-1)/m ≤ n/m ≤ 1/2这是整个推导链的地基。如果装载因子 α 接近 1期望探测次数会急剧恶化由定理 11.6不成功查找的期望探测次数为 1/(1-α)当 α → 1 时趋于无穷仓库配套习题 11.4-3 也量化了这一点α 3/4 时不成功查找期望 4 次探测α 7/8 时升至 8 次。11.4-5 进一步求出不成功查找期望恰好等于成功查找期望两倍的装载因子 α ≈ 0.71533。相比之下本问题在 α ≤ 1/2 的约束下给出了最长探测序列期望仅 O(lg n)的强得多的结论——这正是教科书将表是否过半满作为开放寻址实用准则的原因一旦装载因子超过 1/2长探测序列的出现频率就会明显上升。相关习题与延伸阅读仓库内本问题与仓库第 11 章的多个题目形成对照适合串联阅读11.4-1用线性探测、二次探测c₁ 1, c₂ 3与双重散列h₁(k) k, h₂(k) 1 (k mod (m-1))在 m 11 的表上插入 9 个键直观展示了三种探测序列的差异也暴露了二次探测仅能覆盖偶数偏移导致键 59 无法插入的缺陷11.4-2给出 HASH-DELETE 与改进版 HASH-INSERT 的伪代码说明开放寻址删除时需引入特殊标记 DELETE并在插入时把该标记视为空槽Problem 11-2链地址法下的最长链期望分析结论为 E[M] O(lg n / lg lg n)与本问题的 O(lg n) 形成有趣对比——开放寻址的最长探测序列期望O(lg n)比链地址法的最长链期望O(lg n / lg lg n)多一个 lg lg n 因子11.5-1开放寻址下 n 次插入无冲突的概率 p(n, m) ≤ e^{-n(n-1)/(2m)}即当 n 超过 √m 时冲突几乎不可避免从生日问题视角佐证了本问题中探测序列存在的必然性Problem 11-3 与 Problem 11-4涉及探测策略的遍历性与 k-全域k-universal散列族其中 11-4 的 (d) 问还给出了一个基于 2-全域散列的消息认证应用展示了散列分析在密码学场景中的价值。小结Problem 11-1 通过四个递进的小问完整刻画了开放寻址散列表在均匀散列 装载因子 ≤ 1/2条件下的最长探测序列行为单次插入探测超过 k 次的概率至多 $2^{-k}$指数尾界单次插入探测超过 $2\lg n$ 次的概率为 $O(1/n^2)$全程最长探测序列超过 $2\lg n$ 次的概率为 $O(1/n)$最长探测序列的期望长度为 $O(\lg n)$。这套证明方法条件概率链式放缩 → 多项式尾概率 → 联合界 → 尾和公式是《算法导论》概率分析章节的典型范式也可迁移到负载均衡、随机图等最坏单元分析场景。仓库原文在 docs/Chap11/Problems/11-1.md 保留了完整题面解答标注为 Removed本文的推导可作为阅读题面后的对照参考相关配套习题请见 11.4.md、11.5.md 与 Problems 目录。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 11 章 Hash Tables 难题详解开放寻址最长探查序列与链地址法槽位上限的期望界CLRS 第 11 章 Hash Tables 难题详解开放寻址最长探查序列与链地址法槽位上限的期望界 本篇技术文章以 CLRS《算法导论》第 11 章文档教程示例工程CLRS 第 11.4 节开放寻址Open Addressing习题全解线性探测、二次探测、双重散列与期望探针分析CLRS 第 11.4 节开放寻址Open Addressing习题全解线性探测、二次探测、双重散列与期望探针分析 导读 本文围绕《算法导论第三版》第文档教程教育开放寻址散列无冲突概率上界11.5-1 的数学归纳证明与工程启示开放寻址散列无冲突概率上界11.5 1 的数学归纳证明与工程启示 导读 本文围绕《算法导论》Introduction to Algorithms第 11文档教程示例工程上一篇把十年QQ空间完整搬进本地QQ空间备份工具一键导出免费教程下一篇DLSS Swapper 完整使用教程3 步给游戏切换 DLSS/FSR/XeSS 版本创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考