简介Sariel Har-Peled 的《随机算法》是一本面向已具备算法基础和证明能力的读者的经典讲义围绕随机算法的定义、优势与适用场景展开重点说明随机化如何让算法在对抗性环境和复杂优化中更具效率与鲁棒性。资源为 PDF 文档压缩包内仅 1 个文件大小 8.78MB。内容从“三硬币游戏”这一经典例子切入先讨论随机化带来的不可预测性再系统介绍样本空间、σ-代数、概率测度、期望和条件概率等概率基础同时严格区分随机算法与平均情况分析指出后者依赖输入分布假设而前者对任意输入均可分析。书中还包含快速排序与二叉空间分割等典型随机化实例体现随机方法在排序和几何数据结构中的实际价值。读者可借助这些内容理解随机化如何突破确定性下界并掌握随机算法设计、去随机化与证明的基本方法。该资源目前已有 113 人学习/下载适合希望深入算法设计与分析的中高级读者作为专题研读材料。1. 这份《随机算法》PDF到底值不值得啃先回答三个现实问题“随机算法”这份PDF在算法圈子里流传了很多年但真正把它从头读到尾的人并不多。先给结论这份PDF不是给人当科普读物看的它是一份研究生级别的讲义讲的是“怎么用随机性把算法的期望复杂度打下来”以及“怎么证明这件事”。如果你只想刷LeetCode它不一定能直接帮忙但如果你要做分布式系统、数据库索引、图算法或者安全方向的工程里面关于跳跃表、哈希指纹和尾界的内容能让你比只会调参的人多看到一层本质。这篇笔记我会把它当一份“可以动手跑”的资料来拆先讲读它需要什么底子再划重点内容最后给三个能直接跑通的代码案例和五个常见的翻车点。适合想在随机算法上真正上个台阶的开发者或研究生。2. 读这份PDF前必须补的三块底子概率论、算法复杂度与数学功底随机算法这份PDF对读者的假设是有基础算法设计和分析能力但很多人在第一章就栽了因为概率论符号像天书。其实它需要的概率论并不深但概念必须“活”——不是会背公式而是知道什么时候用哪个不等式。这一章我把最关键的底子拆成三块每一块都给出自测标准和阅读策略。2.1 概率论到底要学到什么程度期望、方差、切比雪夫与切尔诺夫界先说结论你不需要会做复杂的概率密度积分但必须熟练掌握离散随机变量的期望、方差、指示变量以及三个不等式马尔可夫、切比雪夫、切尔诺夫界。这份PDF在分析随机算法时基本套路都是“先算期望再证明结果集中在期望附近”。期望线性E[XY]E[X]E[Y]即使X和Y相关也成立。这是随机算法分析里最常用、也最容易被忽略的“免费午餐”。比如分析快速排序时把总比较次数拆成每一对元素的比较次数之和靠的就是期望线性。指示变量把“事件是否发生”记为0/1变量期望就等于事件发生的概率。这个技巧在PDF里无处不在。马尔可夫不等式P[X≥t]≤E[X]/t适合粗糙估计。切比雪夫不等式用方差控制偏离P[|X-E[X]|≥t]≤Var(X)/t²适合当你知道方差时。切尔诺夫界当随机变量是许多独立伯努利变量之和时能给出指数级衰减的尾界。这是随机算法“高概率成功”证明的利器。如何自测你是否过关拿一张白纸写出“n个独立伯努利变量之和的切尔诺夫界”的推导思路。如果你只能写出公式但不能说明为什么“指数衰减”来自哪里那建议先补一补。我一般建议读者在进入这份PDF之前先把这三个不等式的证明各自推一遍证明过程本身不长但对理解PDF的证明语言帮助很大。这一节的真正重点不是背诵而是建立“界”的感觉随机算法的运行时间是一个随机变量我们既可以说“期望是O(n log n)”也可以说“以至少1-1/n的概率运行时间不超过某个值”。两者是完全不同的断言后面会反复出现。如果不想翻教材可以用一个小程序模拟抛硬币直接观察切尔诺夫界的指数衰减。比如抛n次公平硬币统计正面次数偏离n/2超过εn的概率随着n增大这个概率下降的趋势。这比单纯看公式更直观也能帮你理解为什么随机算法需要足够多的独立重复才能高概率成功。2.2 算法分析的基本功摊还分析、平摊期望与高概率结论怎么读很多读者是第一次接触“随机化快速排序”看到定理说“期望O(n log n)”以为这就是所有输入下的时间上界。这是最大的误解。期望运行时间是在随机选择比如随机pivot下对随机变量求期望但最坏情况下比如你随机数发生器恰好一直选到最坏pivot概率极小但非零仍然可能O(n²)。所以这份PDF里除了期望分析还特别强调“以高概率”的结论。所谓高概率通常指失败概率可以降到1/n^cc为常数。这种结论比期望更有用因为它能保证几乎每次运行都很快而期望可能被极少数极端情况拉高。读PDF时看到“expected running time”和“with high probability”要停下来想清楚两者的强弱关系。摊还分析在这里的作用是当我们反复执行某个随机数据结构比如跳跃表的操作时单次操作可能慢但分摊到整个序列上是快的。这份PDF里的哈希表和跳跃表章节就会同时用到概率分析和摊还视角。建议读者先自己用数组实现一次动态表扩张理解“为什么每次插入均摊O(1)”再去看跳跃表的分析会顺手很多。在工程里“高概率”比“期望”更贴近真实需求。比如一个爬虫系统要抓取大量URL如果某个节点的负载是期望值但方差很大监控告警会被打得措手不及而高概率边界告诉你99.9%的情况下不会超过某个阈值。这份PDF里的切比雪夫和切尔诺夫界就是推导这些边界的工具。如果你概率论基础很弱不要先从第一章开始啃。很多读过的人建议先把高数里的“期望和方差”复习完然后直接跳到跳跃表章节动手写代码再回来啃证明。这个顺序能让你带着“为什么需要随机化”的问题去读前面的抽象内容。2.3 数学符号与证明风格的“翻译”这份PDF的记号体系和阅读技巧随机算法PDF的记号其实很标准Pr[·]表示概率E[·]表示期望Var[·]表示方差用I_{A}表示事件A的指示变量。但真正的阅读门槛不是记号本身而是证明里那种“先定义一个随机变量然后用一串不等式放缩”的节奏。很多人在第一个证明里就迷路因为不知道哪些步骤可以跳过。我的阅读习惯是分三层第一层只看定理陈述和例子理解算法在解决什么问题第二层看证明的结构标出“它用了期望线性还是独立性还是尾界”第三层才是逐行验证放缩。这份PDF里有些证明写得比较省略比如“by Chernoff bound”一句话带过这时候你要自己补上参数。补参数的过程很花时间但也是收获最大的地方。另外PDF是讲义性质的可能有排版小问题、笔误、或者基于旧版LaTeX不同版本编译效果不一样。有些公式的上下标看不清别死磕去找同时代的其他教材对照。我遇到过有人因为一个印刷不清的指数符号白耗了两天。遇到不确定的记号先跳过看看后面用它的地方能不能反推含义。建议准备一个“符号对照表”的笔记把PDF里出现的所有符号和含义记下来。虽然它不像某些书那样符号密到爆炸但在后面处理多随机变量时很容易把X_i和X^{(i)}搞混。我自己一般用不同颜色标注“随机变量”和“确定性值”看证明时思路会清晰很多。3. 把讲义拆成四块核心内容从随机化快速排序到最小割算法这一章是内容精华。我把这份PDF最常被引用、也最值得反复消化的四个算法单独拎出来。它们分别代表了随机算法的四种典型作用消除最坏情况、压缩信息、构建低维护成本的数据结构、以重复换取高概率成功。每一点都能直接映射到工程问题。3.1 随机化快速排序与期望分析为什么随机化能让最坏情况消失随机化快速排序是这份PDF第一个重量级例子。经典快速排序如果每次选最后一个元素遇到已排序输入会退化到O(n²)。随机化做法是每次均匀随机选一个元素作为pivot。这样任何固定输入都无法让算法稳定地踩中最坏情况算法的期望运行时间变成O(n log n)。为什么随机化有效关键是把“输入导致最坏情况”这个确定性矛盾转变成“随机选择的罕见事件”。对于一个固定输入最坏情况只有在每次随机pivot恰好都选到当前区间的极值时才会发生这个概率极小。这里最漂亮的证明是使用指示变量设X_ij表示第i小和第j小元素是否在排序过程中被比较一次利用期望线性得到总比较次数期望为O(n log n)。这个证明不用复杂的条件概率就是期望线性积分近似。落地价值很多排序场景中数据分布是未知的甚至可能被恶意构造。用随机化快速排序至少不会被固定输入套路。但要注意随机化不等于完全免疫最坏情况只是把最坏情况变成概率极低。如果你要的是真正的确定性保证需要选择最坏情况O(n log n)的归并排序或堆排序。这是我读PDF时学会的第一课随机化改变的是风险分布不是消除风险。随机化快速排序还有一个变形叫随机快速选择用于在未排序数组中找第k大元素期望O(n)。它的证明思路和快速排序类似但只需要递归一侧。这个算法在计算中位数、负载均衡的“分位数估计”等场景非常实用PDF后面的习题里也会出现。建议读者把它和快速排序一起实现对比两者的随机化作用。3.2 哈希与指纹随机算法在字符串匹配和集合相等性判断上的落地哈希是随机算法在工程里最常见的形态。这份PDF会讲两类一类是哈希表用随机哈希函数把key分布到桶里另一类是“指纹”就是把一个长字符串映射成一个短数字然后用比较数字代替比较字符串。指纹的经典应用是字符串匹配判断两个文件是否相等不用逐字节比较而是比较它们的随机指纹。更巧妙的用法是在通信和分布式系统里传输大文件前先传指纹相等就直接跳过。指纹的关键性质是如果两个对象相等指纹必然相等如果不等指纹相等的概率即碰撞或错误匹配可以被控制在极小的范围内。通过选取足够大的随机模数和随机基错误率可以低于你电脑硬件故障的概率。我见过很多人在工程中直接用语言运行时默认的哈希函数来做指纹这是有风险的因为默认哈希函数不一定具备我们想要的随机性保证而且恶意输入可能制造碰撞攻击。PDF里讲的是用随机选取的素数取模并保证指纹长度远大于数据规模的对数这样碰撞概率才有尾部保证。落地时可以用带随机盐值的非加密哈希来近似这个思想。这一节的算法代码在工程里非常好用建议重点掌握。指纹算法还有一个经典场景是“判断两个大集合是否相等”。比如两个服务器各存一个大的集合想在不传输全部元素的情况下确认是否相同可以用一个随机多项式对每个元素生成一个指纹然后比较乘积。碰撞概率可以通过选择随机系数和模数压到极低。这个“代数指纹”的数学基础是概率论里的多项式恒等判定引理PDF里有专门章节讨论。工程上可以把这当作一种比布隆过滤器更精确的概率性集合比较方案但它对模数的选择更敏感。3.3 跳跃表与随机平衡结构工程里最常见的随机化数据结构跳跃表是这份PDF里最“工程友好”的随机数据结构之一它的插入、删除、查找期望都是O(log n)而且实现比红黑树简单太多。它的核心是用随机掷硬币决定每个节点出现在多少层。每个节点有一个levellevelk的概率为1/2^{k-1}这样整张表的期望层数是2层起。为什么随机层数有效因为每个节点的层高是独立的即使输入有序层的分布也不会被预测。查找时从最高层往下走每一层都跳过大量节点期望步数O(log n)。对比红黑树需要维护颜色和旋转跳跃表只需要维护前后指针工程上调试成本低很多。很多内存数据库的有序集合底层就是跳跃表。不过跳跃表有一个坑随机数发生器质量差时层高分布可能偏差导致性能退化。读PDF时大家通常会关注期望分析却忽略了“独立且均匀”的假设。在工程里用C库的rand()可能不够随机有时代码正确但性能不达标就是因为随机源太弱。建议在实现时用独立的高质量伪随机数发生器并在测试时固定种子以便复现。数据库的LSM-tree、内存中的有序集合都用了跳跃表思想。读PDF时理解“层高几何分布”是核心。很多面试题会问“为什么跳跃表用二分之一的概率向上提升”——答案是为了让每层节点数期望减半从而实现log n量级的层数。如果你把概率改成1/3不是不行只是常数项变了改成固定值反而失去随机化的意义。3.4 全局最小割的随机收缩算法随机算法以高概率成功的经典这份PDF里我印象最深的算法是全局最小割的随机收缩算法。给定一个无向图要找到最少边数能把图分成两部分的割。传统上要用最大流每次O(n^3)。随机收缩算法则极其简单随机选一条边把它的两个端点收缩成一个点不断重复直到只剩两个点最后剩下的边就是候选割。重复这个过程足够多次取最小的结果。为什么这么简单的方法有效因为最小割的边数相对较少每次随机选边时大概率不会选中最小割的边。每一步不选中最小割边的概率至少是1-2/(当前顶点数)连乘之后一次收缩成功得到最小割的概率约为1/n^2。于是重复n^2乘以一个对数因子次就能以高概率找到全局最小割。这个证明把“随机化”和“高概率成功”的关系展示得淋漓尽致单次尝试成功率很低但重复次数可以换取成功概率。落地价值这个算法在超大规模图数据集上没法直接跑但它体现的“随机收缩重复”思想很强大。比如在社交网络里做社区检测的粗化阶段经常能看到类似的随机合并策略。读这一段时一定要自己推导一遍“每一步不选中最小割的概率”再跑一遍代码否则只看证明容易觉得“这怎么能行”。随机收缩算法的另一个关键是“重边”的处理。收缩时如果两个端点之间有重边这些边会叠加成一条更粗的边最后候选割的权重是所有平行边之和。所以实现时通常用邻接矩阵维护边权而不是简单删边。这一点PDF里没有明说但写代码时一定会踩到。4. 把PDF里的算法写成代码三个可以直接跑的通吃案例前面讲了原理这一章直接落地。我选了三个有代表性的算法随机化快速排序、随机素性检测、随机收缩最小割。它们分别展示了随机算法在排序、数论和图论里的典型写法。代码都是Python逻辑尽量精简方便直接跑。4.1 随机化快速排序三行核心逻辑与随机种子的选择import random def randomized_quicksort(arr): if len(arr) 1: return arr pivot_idx random.randint(0, len(arr) - 1) pivot arr[pivot_idx] left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return randomized_quicksort(left) mid randomized_quicksort(right)这个版本用列表推导做分区每次递归都重新遍历三遍数组空间开销大但逻辑清晰。pivot_idx是随机生成的坐标这是随机化的唯一关键点。随机种子设置在调试时建议在脚本开头random.seed(42)让每次运行的随机序列一致便于定位问题。而在正式跑性能对比时不要固定种子应该用系统熵源否则你的基准测试只是在测试同一组伪随机数。参数说明递归深度最坏情况下可能到n所以Python默认递归深度1000可能不够。处理大数组时要么改成迭代版要么用sys.setrecursionlimit()。另外这个实现里的mid用于处理重复元素避免重复元素导致左右不均。如果你用random.shuffle先洗牌再取第一个元素也是一种随机化但shuffle本身有额外开销直接随机选pivot更高效。还有别在递归里重置随机种子否则每次pivot都一样随机化就白做了。如果不想用额外空间可以参考原地分区版本但随机化核心是一样的。原地版本需要先选pivot再交换到最右端然后用双指针分区。面试时用列表推导版本简单清晰但实际库函数例如sorted()用Timsort不在此列。随机化快速排序更适合教学和定制场景。4.2 随机素性检测蒙特卡洛算法的典型参数设置import random def is_probable_prime(n, k10): if n 2: return False # 小因子检查 for p in (2, 3, 5, 7, 11, 13, 17, 19): if n % p 0: return n p # 把 n-1 写成 d * 2^s d n - 1 s 0 while d % 2 0: s 1 d // 2 for _ in range(k): a random.randint(2, n - 2) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x pow(x, 2, n) if x n - 1: break else: return False return True逻辑说明这是一种蒙特卡洛的素性检测方法输出“合数”是确定的输出“素数”是大概率的。k是随机基底数量每增加一个基底误判概率最多除以4。k10时误判率低于四的十次方分之一约百万分之一。如果需要对抗性输入或更高安全级别k可以取40。参数说明d和s的分解是固定的随机基底a从2到n-2均匀选取。在Python中pow(x, y, n)是快速模幂避免大整数直接乘方爆炸。注意对于小偶数先做小因子检查能显著加速。如果n是32位以内整数k3其实够用但如果n是几百位的大整数k至少40。这里有个翻车点有些人为了可复现固定random.seed后测试发现某个大素数被误判为合数就以为算法错了。其实这种随机算法依赖随机选基底固定种子后你只是在测那一个确定的序列。正确做法是跑多轮或者用系统随机源。为了验证误判率可以写一个测试对小于1000的所有合数调用is_probable_prime统计k取1、2、3时的误判次数。你会发现即使k1误判率也远低于理论界因为理论界是最坏情况实际数据通常更友好。但不要因此就把k设得很小对抗性输入会让你翻车。有一些特殊合数能满足几乎所有随机基底的检测条件这种检测里的二次探测步骤正是为了对付它们所以基底数量不能省。4.3 全局最小割的随机收缩算法重复次数与随机数生成器的影响import random import math def random_contraction_min_cut(edges, n): # edges: list of (u, v), 无向图, 顶点编号 0..n-1 best float(inf) # 重复次数 n^2 * ln n repeat int(n * n * math.log(n)) for _ in range(repeat): parent list(range(n)) # 并查集维护收缩后的顶点 def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): rx, ry find(x), find(y) if rx ry: return False parent[ry] rx return True edge_list edges[:] order list(range(len(edge_list))) random.shuffle(order) remaining n while remaining 2: idx order.pop() # 模拟随机选边 u, v edge_list[idx] if not union(u, v): continue # 自环忽略 remaining - 1 # 最终割边 连接两个分量的边数 cut 0 for u, v in edge_list: if find(u) ! find(v): cut 1 best min(best, cut) return best逻辑说明这个实现用并查集维护收缩后的顶点。每次random.shuffle打乱边顺序然后依次取边遇到自环就跳过。remaining记录当前顶点数每成功合并一条边就减一。重复次数是理论上要求的repeat直接由 n 计算得到。代码中最容易出错的是收缩后顶点数追踪这里用remaining变量而不是直接修改传入的 n。参数说明repeat是重复尝试次数直接影响成功概率。按照PDF里的分析单次成功的概率约1/(n^2)所以重复c * n^2 * ln n次能让失败概率降到O(n^{-c})。random.shuffle的均匀性很重要如果随机源有偏结果会不稳。调试时固定random.seed但发表实验结果时必须用多个种子取平均。另外边的存储方式决定了重边是否保留用(u, v)对无法保存重边如果图本身有重边应该用多重边列表。生成一个测试图比如n20用随机生成器产生若干边确保连通。然后跑这个函数对比用现成图算法库算出的真实最小割你会发现重复次数里的对数因子是必须的如果只重复n^2次偶尔会失败加上ln n因子后多跑几次不会失败。这个实验能直观感受“对数因子”在概率上的作用。随机算法的性能有时候像玄学但边界是能推出来的不要靠感觉调参。5. 避坑指南读这份PDF时最常翻车的五个点这份PDF的价值很大但阅读过程中的“坑”也不少。我总结了五个高频翻车点都是血泪经验每条按现象、原因、解决来写希望能帮你少走弯路。5.1 现象卡在第一章的数学符号进度停滞现象翻开PDF第一页“定义 1.1”、Pr[]、E[]、i.i.d.以及各种不等式读了半小时书还在第一页。原因这份PDF是讲义默认读者已经学过概率论。它不是教材没有耐心从零教微积分。如果你把每个符号都查一遍再往下走等于在读一本字典。解决第一次阅读直接跳到跳跃表或随机化快速排序那里有具体的算法和证明。遇到看不懂的符号先猜含义或者查前面的定义不恋战。读完算法再回头补概率论。如果你连期望、独立性都忘光了花一天时间快速过一遍大学概率论笔记比硬啃PDF效率高得多。5.2 现象把“期望运行时间”当成“最坏运行时间”来理解现象看到“期望O(n log n)”就放心地在实时系统里使用结果偶尔一次运行时间突然飙到几十倍导致超时。原因期望不等于上界。随机算法的一小部分随机路径可能非常慢虽然概率低但在你不能容忍尾延迟的系统中必须考虑高概率边界。解决读PDF时对每个定理先问这里给的是期望界还是高概率界如果是期望界能否用切尔诺夫界推出更严格的高概率界在工程实现时对随机化快速排序、随机哈希表等要设置超时保护或者采用多算法冗余而不是盲目相信期望值。5.3 现象自己推导证明时乱用独立性假设现象在证明跳跃表某层节点数的期望时自己把“每个节点是否在第k层”当成独立事件算出错误的方差。原因节点的层高是独立抽取的但“在第k层出现”这个事件确实独立而“第k层节点数”是这些独立指示变量之和独立性成立。但在别的算法里比如随机收缩过程各条边是否被选中是相关的不能直接用独立乘积。解决每次使用“和的方差方差之和”前检查协方差是否为0。更稳妥的风格是在证明中写下“这些事件是独立的因为……”写不出来就改用并界或条件期望。这份PDF中的证明经常默认读者能看出独立性看不出就去翻概率论课本。5.4 现象随机算法在本地跑的结果不稳定怀疑程序写错了现象同一个输入运行五次得到五次不同的结果有时正确有时错误开始怀疑代码有bug。原因随机算法本身就有随机性输出或运行时间有波动是正常的。但你可能会把“算法正确性概率”和“实现bug”混淆。比如随机收缩算法单次运行很可能得不到最小割这不是bug而是重复次数不够。解决先固定随机种子复现结果确认逻辑一致性。然后用统计视角看待多跑几十次看结果的分布。如果是正确性概率问题就提高重复次数如果是运行时间波动就检查是否触发了最坏随机路径。这条“统计调试”习惯是读这份PDF之后最大的收获。5.5 现象把讲义当小说读不写代码看过就忘现象一个月前读过跳跃表那一章感觉懂了现在面试被问“层高为什么是几何分布”支支吾吾。原因讲义里的定理推导是“输入到输出”的路径你没有亲手构建这个路径。看证明就像看别人打游戏自己上场还是迷路。解决读每个算法的当天必须写一个最小实现并做一个对照实验。比如跳跃表你要亲眼看到插入一万个随机节点后的层级分布符合几何分布随机收缩算法你要看到重复次数增加时成功概率的上升趋势。这样做完你才算真正“拥有”了这个知识。看PDF不是目的能自己推、能自己写、能在项目里选型才是目的。6. 把这份PDF读成你的竞争力从习题到面试的一个具体训练套路如果你和我一样不是为了读PDF而读而是想把随机算法变成面试里的谈资、工程里的武器我给你一个可复制的训练套路三步消化法。以跳跃表为例。第一步读PDF里关于跳跃表的那一章先用纸笔推演“期望层高为什么是O(log n)”。别急着打开电脑推演过程能让你发现哪些符号没吃透。第二步写一个包含插入和查找的最小实现固定随机种子插入一万个随机key统计各层的节点数画出来看是否符合几何分布。第三步做一个随机数据下的性能对比实验分别用跳跃表和有序数组执行同样次数的查找记录耗时数据点。你会发现有序数组的二分查找虽然O(log n)但常数极小跳跃表常数较大但插入和删除更快。这个对比结论面试里能讲出层次。我自己以前偷懒跳跃表这种结构只看了结论就跳过结果有一次在模拟项目里需要频繁插入删除且有序遍历我用了数组加二分插入导致大量元素移动性能翻车。后来用这份PDF的方法把证明和代码一起过了一遍才明白跳跃表的价值不在单次查询而在“插入查找删除”的期望均衡。现在我的习惯是读完一个随机算法先写一个带随机种子的最小复现再做一次至少三组参数的对比实验然后才在真正项目里参考它。这套习惯帮我省了很多“以为会了”的后悔药。希望帮到你。本文还有配套的精品资源点击获取
简介Sariel Har-Peled 的《随机算法》是一本面向已具备算法基础和证明能力的读者的经典讲义围绕随机算法的定义、优势与适用场景展开重点说明随机化如何让算法在对抗性环境和复杂优化中更具效率与鲁棒性。资源为 PDF 文档压缩包内仅 1 个文件大小 8.78MB。内容从“三硬币游戏”这一经典例子切入先讨论随机化带来的不可预测性再系统介绍样本空间、σ-代数、概率测度、期望和条件概率等概率基础同时严格区分随机算法与平均情况分析指出后者依赖输入分布假设而前者对任意输入均可分析。书中还包含快速排序与二叉空间分割等典型随机化实例体现随机方法在排序和几何数据结构中的实际价值。读者可借助这些内容理解随机化如何突破确定性下界并掌握随机算法设计、去随机化与证明的基本方法。该资源目前已有 113 人学习/下载适合希望深入算法设计与分析的中高级读者作为专题研读材料。1. 这份《随机算法》PDF到底值不值得啃先回答三个现实问题“随机算法”这份PDF在算法圈子里流传了很多年但真正把它从头读到尾的人并不多。先给结论这份PDF不是给人当科普读物看的它是一份研究生级别的讲义讲的是“怎么用随机性把算法的期望复杂度打下来”以及“怎么证明这件事”。如果你只想刷LeetCode它不一定能直接帮忙但如果你要做分布式系统、数据库索引、图算法或者安全方向的工程里面关于跳跃表、哈希指纹和尾界的内容能让你比只会调参的人多看到一层本质。这篇笔记我会把它当一份“可以动手跑”的资料来拆先讲读它需要什么底子再划重点内容最后给三个能直接跑通的代码案例和五个常见的翻车点。适合想在随机算法上真正上个台阶的开发者或研究生。2. 读这份PDF前必须补的三块底子概率论、算法复杂度与数学功底随机算法这份PDF对读者的假设是有基础算法设计和分析能力但很多人在第一章就栽了因为概率论符号像天书。其实它需要的概率论并不深但概念必须“活”——不是会背公式而是知道什么时候用哪个不等式。这一章我把最关键的底子拆成三块每一块都给出自测标准和阅读策略。2.1 概率论到底要学到什么程度期望、方差、切比雪夫与切尔诺夫界先说结论你不需要会做复杂的概率密度积分但必须熟练掌握离散随机变量的期望、方差、指示变量以及三个不等式马尔可夫、切比雪夫、切尔诺夫界。这份PDF在分析随机算法时基本套路都是“先算期望再证明结果集中在期望附近”。期望线性E[XY]E[X]E[Y]即使X和Y相关也成立。这是随机算法分析里最常用、也最容易被忽略的“免费午餐”。比如分析快速排序时把总比较次数拆成每一对元素的比较次数之和靠的就是期望线性。指示变量把“事件是否发生”记为0/1变量期望就等于事件发生的概率。这个技巧在PDF里无处不在。马尔可夫不等式P[X≥t]≤E[X]/t适合粗糙估计。切比雪夫不等式用方差控制偏离P[|X-E[X]|≥t]≤Var(X)/t²适合当你知道方差时。切尔诺夫界当随机变量是许多独立伯努利变量之和时能给出指数级衰减的尾界。这是随机算法“高概率成功”证明的利器。如何自测你是否过关拿一张白纸写出“n个独立伯努利变量之和的切尔诺夫界”的推导思路。如果你只能写出公式但不能说明为什么“指数衰减”来自哪里那建议先补一补。我一般建议读者在进入这份PDF之前先把这三个不等式的证明各自推一遍证明过程本身不长但对理解PDF的证明语言帮助很大。这一节的真正重点不是背诵而是建立“界”的感觉随机算法的运行时间是一个随机变量我们既可以说“期望是O(n log n)”也可以说“以至少1-1/n的概率运行时间不超过某个值”。两者是完全不同的断言后面会反复出现。如果不想翻教材可以用一个小程序模拟抛硬币直接观察切尔诺夫界的指数衰减。比如抛n次公平硬币统计正面次数偏离n/2超过εn的概率随着n增大这个概率下降的趋势。这比单纯看公式更直观也能帮你理解为什么随机算法需要足够多的独立重复才能高概率成功。2.2 算法分析的基本功摊还分析、平摊期望与高概率结论怎么读很多读者是第一次接触“随机化快速排序”看到定理说“期望O(n log n)”以为这就是所有输入下的时间上界。这是最大的误解。期望运行时间是在随机选择比如随机pivot下对随机变量求期望但最坏情况下比如你随机数发生器恰好一直选到最坏pivot概率极小但非零仍然可能O(n²)。所以这份PDF里除了期望分析还特别强调“以高概率”的结论。所谓高概率通常指失败概率可以降到1/n^cc为常数。这种结论比期望更有用因为它能保证几乎每次运行都很快而期望可能被极少数极端情况拉高。读PDF时看到“expected running time”和“with high probability”要停下来想清楚两者的强弱关系。摊还分析在这里的作用是当我们反复执行某个随机数据结构比如跳跃表的操作时单次操作可能慢但分摊到整个序列上是快的。这份PDF里的哈希表和跳跃表章节就会同时用到概率分析和摊还视角。建议读者先自己用数组实现一次动态表扩张理解“为什么每次插入均摊O(1)”再去看跳跃表的分析会顺手很多。在工程里“高概率”比“期望”更贴近真实需求。比如一个爬虫系统要抓取大量URL如果某个节点的负载是期望值但方差很大监控告警会被打得措手不及而高概率边界告诉你99.9%的情况下不会超过某个阈值。这份PDF里的切比雪夫和切尔诺夫界就是推导这些边界的工具。如果你概率论基础很弱不要先从第一章开始啃。很多读过的人建议先把高数里的“期望和方差”复习完然后直接跳到跳跃表章节动手写代码再回来啃证明。这个顺序能让你带着“为什么需要随机化”的问题去读前面的抽象内容。2.3 数学符号与证明风格的“翻译”这份PDF的记号体系和阅读技巧随机算法PDF的记号其实很标准Pr[·]表示概率E[·]表示期望Var[·]表示方差用I_{A}表示事件A的指示变量。但真正的阅读门槛不是记号本身而是证明里那种“先定义一个随机变量然后用一串不等式放缩”的节奏。很多人在第一个证明里就迷路因为不知道哪些步骤可以跳过。我的阅读习惯是分三层第一层只看定理陈述和例子理解算法在解决什么问题第二层看证明的结构标出“它用了期望线性还是独立性还是尾界”第三层才是逐行验证放缩。这份PDF里有些证明写得比较省略比如“by Chernoff bound”一句话带过这时候你要自己补上参数。补参数的过程很花时间但也是收获最大的地方。另外PDF是讲义性质的可能有排版小问题、笔误、或者基于旧版LaTeX不同版本编译效果不一样。有些公式的上下标看不清别死磕去找同时代的其他教材对照。我遇到过有人因为一个印刷不清的指数符号白耗了两天。遇到不确定的记号先跳过看看后面用它的地方能不能反推含义。建议准备一个“符号对照表”的笔记把PDF里出现的所有符号和含义记下来。虽然它不像某些书那样符号密到爆炸但在后面处理多随机变量时很容易把X_i和X^{(i)}搞混。我自己一般用不同颜色标注“随机变量”和“确定性值”看证明时思路会清晰很多。3. 把讲义拆成四块核心内容从随机化快速排序到最小割算法这一章是内容精华。我把这份PDF最常被引用、也最值得反复消化的四个算法单独拎出来。它们分别代表了随机算法的四种典型作用消除最坏情况、压缩信息、构建低维护成本的数据结构、以重复换取高概率成功。每一点都能直接映射到工程问题。3.1 随机化快速排序与期望分析为什么随机化能让最坏情况消失随机化快速排序是这份PDF第一个重量级例子。经典快速排序如果每次选最后一个元素遇到已排序输入会退化到O(n²)。随机化做法是每次均匀随机选一个元素作为pivot。这样任何固定输入都无法让算法稳定地踩中最坏情况算法的期望运行时间变成O(n log n)。为什么随机化有效关键是把“输入导致最坏情况”这个确定性矛盾转变成“随机选择的罕见事件”。对于一个固定输入最坏情况只有在每次随机pivot恰好都选到当前区间的极值时才会发生这个概率极小。这里最漂亮的证明是使用指示变量设X_ij表示第i小和第j小元素是否在排序过程中被比较一次利用期望线性得到总比较次数期望为O(n log n)。这个证明不用复杂的条件概率就是期望线性积分近似。落地价值很多排序场景中数据分布是未知的甚至可能被恶意构造。用随机化快速排序至少不会被固定输入套路。但要注意随机化不等于完全免疫最坏情况只是把最坏情况变成概率极低。如果你要的是真正的确定性保证需要选择最坏情况O(n log n)的归并排序或堆排序。这是我读PDF时学会的第一课随机化改变的是风险分布不是消除风险。随机化快速排序还有一个变形叫随机快速选择用于在未排序数组中找第k大元素期望O(n)。它的证明思路和快速排序类似但只需要递归一侧。这个算法在计算中位数、负载均衡的“分位数估计”等场景非常实用PDF后面的习题里也会出现。建议读者把它和快速排序一起实现对比两者的随机化作用。3.2 哈希与指纹随机算法在字符串匹配和集合相等性判断上的落地哈希是随机算法在工程里最常见的形态。这份PDF会讲两类一类是哈希表用随机哈希函数把key分布到桶里另一类是“指纹”就是把一个长字符串映射成一个短数字然后用比较数字代替比较字符串。指纹的经典应用是字符串匹配判断两个文件是否相等不用逐字节比较而是比较它们的随机指纹。更巧妙的用法是在通信和分布式系统里传输大文件前先传指纹相等就直接跳过。指纹的关键性质是如果两个对象相等指纹必然相等如果不等指纹相等的概率即碰撞或错误匹配可以被控制在极小的范围内。通过选取足够大的随机模数和随机基错误率可以低于你电脑硬件故障的概率。我见过很多人在工程中直接用语言运行时默认的哈希函数来做指纹这是有风险的因为默认哈希函数不一定具备我们想要的随机性保证而且恶意输入可能制造碰撞攻击。PDF里讲的是用随机选取的素数取模并保证指纹长度远大于数据规模的对数这样碰撞概率才有尾部保证。落地时可以用带随机盐值的非加密哈希来近似这个思想。这一节的算法代码在工程里非常好用建议重点掌握。指纹算法还有一个经典场景是“判断两个大集合是否相等”。比如两个服务器各存一个大的集合想在不传输全部元素的情况下确认是否相同可以用一个随机多项式对每个元素生成一个指纹然后比较乘积。碰撞概率可以通过选择随机系数和模数压到极低。这个“代数指纹”的数学基础是概率论里的多项式恒等判定引理PDF里有专门章节讨论。工程上可以把这当作一种比布隆过滤器更精确的概率性集合比较方案但它对模数的选择更敏感。3.3 跳跃表与随机平衡结构工程里最常见的随机化数据结构跳跃表是这份PDF里最“工程友好”的随机数据结构之一它的插入、删除、查找期望都是O(log n)而且实现比红黑树简单太多。它的核心是用随机掷硬币决定每个节点出现在多少层。每个节点有一个levellevelk的概率为1/2^{k-1}这样整张表的期望层数是2层起。为什么随机层数有效因为每个节点的层高是独立的即使输入有序层的分布也不会被预测。查找时从最高层往下走每一层都跳过大量节点期望步数O(log n)。对比红黑树需要维护颜色和旋转跳跃表只需要维护前后指针工程上调试成本低很多。很多内存数据库的有序集合底层就是跳跃表。不过跳跃表有一个坑随机数发生器质量差时层高分布可能偏差导致性能退化。读PDF时大家通常会关注期望分析却忽略了“独立且均匀”的假设。在工程里用C库的rand()可能不够随机有时代码正确但性能不达标就是因为随机源太弱。建议在实现时用独立的高质量伪随机数发生器并在测试时固定种子以便复现。数据库的LSM-tree、内存中的有序集合都用了跳跃表思想。读PDF时理解“层高几何分布”是核心。很多面试题会问“为什么跳跃表用二分之一的概率向上提升”——答案是为了让每层节点数期望减半从而实现log n量级的层数。如果你把概率改成1/3不是不行只是常数项变了改成固定值反而失去随机化的意义。3.4 全局最小割的随机收缩算法随机算法以高概率成功的经典这份PDF里我印象最深的算法是全局最小割的随机收缩算法。给定一个无向图要找到最少边数能把图分成两部分的割。传统上要用最大流每次O(n^3)。随机收缩算法则极其简单随机选一条边把它的两个端点收缩成一个点不断重复直到只剩两个点最后剩下的边就是候选割。重复这个过程足够多次取最小的结果。为什么这么简单的方法有效因为最小割的边数相对较少每次随机选边时大概率不会选中最小割的边。每一步不选中最小割边的概率至少是1-2/(当前顶点数)连乘之后一次收缩成功得到最小割的概率约为1/n^2。于是重复n^2乘以一个对数因子次就能以高概率找到全局最小割。这个证明把“随机化”和“高概率成功”的关系展示得淋漓尽致单次尝试成功率很低但重复次数可以换取成功概率。落地价值这个算法在超大规模图数据集上没法直接跑但它体现的“随机收缩重复”思想很强大。比如在社交网络里做社区检测的粗化阶段经常能看到类似的随机合并策略。读这一段时一定要自己推导一遍“每一步不选中最小割的概率”再跑一遍代码否则只看证明容易觉得“这怎么能行”。随机收缩算法的另一个关键是“重边”的处理。收缩时如果两个端点之间有重边这些边会叠加成一条更粗的边最后候选割的权重是所有平行边之和。所以实现时通常用邻接矩阵维护边权而不是简单删边。这一点PDF里没有明说但写代码时一定会踩到。4. 把PDF里的算法写成代码三个可以直接跑的通吃案例前面讲了原理这一章直接落地。我选了三个有代表性的算法随机化快速排序、随机素性检测、随机收缩最小割。它们分别展示了随机算法在排序、数论和图论里的典型写法。代码都是Python逻辑尽量精简方便直接跑。4.1 随机化快速排序三行核心逻辑与随机种子的选择import random def randomized_quicksort(arr): if len(arr) 1: return arr pivot_idx random.randint(0, len(arr) - 1) pivot arr[pivot_idx] left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return randomized_quicksort(left) mid randomized_quicksort(right)这个版本用列表推导做分区每次递归都重新遍历三遍数组空间开销大但逻辑清晰。pivot_idx是随机生成的坐标这是随机化的唯一关键点。随机种子设置在调试时建议在脚本开头random.seed(42)让每次运行的随机序列一致便于定位问题。而在正式跑性能对比时不要固定种子应该用系统熵源否则你的基准测试只是在测试同一组伪随机数。参数说明递归深度最坏情况下可能到n所以Python默认递归深度1000可能不够。处理大数组时要么改成迭代版要么用sys.setrecursionlimit()。另外这个实现里的mid用于处理重复元素避免重复元素导致左右不均。如果你用random.shuffle先洗牌再取第一个元素也是一种随机化但shuffle本身有额外开销直接随机选pivot更高效。还有别在递归里重置随机种子否则每次pivot都一样随机化就白做了。如果不想用额外空间可以参考原地分区版本但随机化核心是一样的。原地版本需要先选pivot再交换到最右端然后用双指针分区。面试时用列表推导版本简单清晰但实际库函数例如sorted()用Timsort不在此列。随机化快速排序更适合教学和定制场景。4.2 随机素性检测蒙特卡洛算法的典型参数设置import random def is_probable_prime(n, k10): if n 2: return False # 小因子检查 for p in (2, 3, 5, 7, 11, 13, 17, 19): if n % p 0: return n p # 把 n-1 写成 d * 2^s d n - 1 s 0 while d % 2 0: s 1 d // 2 for _ in range(k): a random.randint(2, n - 2) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x pow(x, 2, n) if x n - 1: break else: return False return True逻辑说明这是一种蒙特卡洛的素性检测方法输出“合数”是确定的输出“素数”是大概率的。k是随机基底数量每增加一个基底误判概率最多除以4。k10时误判率低于四的十次方分之一约百万分之一。如果需要对抗性输入或更高安全级别k可以取40。参数说明d和s的分解是固定的随机基底a从2到n-2均匀选取。在Python中pow(x, y, n)是快速模幂避免大整数直接乘方爆炸。注意对于小偶数先做小因子检查能显著加速。如果n是32位以内整数k3其实够用但如果n是几百位的大整数k至少40。这里有个翻车点有些人为了可复现固定random.seed后测试发现某个大素数被误判为合数就以为算法错了。其实这种随机算法依赖随机选基底固定种子后你只是在测那一个确定的序列。正确做法是跑多轮或者用系统随机源。为了验证误判率可以写一个测试对小于1000的所有合数调用is_probable_prime统计k取1、2、3时的误判次数。你会发现即使k1误判率也远低于理论界因为理论界是最坏情况实际数据通常更友好。但不要因此就把k设得很小对抗性输入会让你翻车。有一些特殊合数能满足几乎所有随机基底的检测条件这种检测里的二次探测步骤正是为了对付它们所以基底数量不能省。4.3 全局最小割的随机收缩算法重复次数与随机数生成器的影响import random import math def random_contraction_min_cut(edges, n): # edges: list of (u, v), 无向图, 顶点编号 0..n-1 best float(inf) # 重复次数 n^2 * ln n repeat int(n * n * math.log(n)) for _ in range(repeat): parent list(range(n)) # 并查集维护收缩后的顶点 def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(x, y): rx, ry find(x), find(y) if rx ry: return False parent[ry] rx return True edge_list edges[:] order list(range(len(edge_list))) random.shuffle(order) remaining n while remaining 2: idx order.pop() # 模拟随机选边 u, v edge_list[idx] if not union(u, v): continue # 自环忽略 remaining - 1 # 最终割边 连接两个分量的边数 cut 0 for u, v in edge_list: if find(u) ! find(v): cut 1 best min(best, cut) return best逻辑说明这个实现用并查集维护收缩后的顶点。每次random.shuffle打乱边顺序然后依次取边遇到自环就跳过。remaining记录当前顶点数每成功合并一条边就减一。重复次数是理论上要求的repeat直接由 n 计算得到。代码中最容易出错的是收缩后顶点数追踪这里用remaining变量而不是直接修改传入的 n。参数说明repeat是重复尝试次数直接影响成功概率。按照PDF里的分析单次成功的概率约1/(n^2)所以重复c * n^2 * ln n次能让失败概率降到O(n^{-c})。random.shuffle的均匀性很重要如果随机源有偏结果会不稳。调试时固定random.seed但发表实验结果时必须用多个种子取平均。另外边的存储方式决定了重边是否保留用(u, v)对无法保存重边如果图本身有重边应该用多重边列表。生成一个测试图比如n20用随机生成器产生若干边确保连通。然后跑这个函数对比用现成图算法库算出的真实最小割你会发现重复次数里的对数因子是必须的如果只重复n^2次偶尔会失败加上ln n因子后多跑几次不会失败。这个实验能直观感受“对数因子”在概率上的作用。随机算法的性能有时候像玄学但边界是能推出来的不要靠感觉调参。5. 避坑指南读这份PDF时最常翻车的五个点这份PDF的价值很大但阅读过程中的“坑”也不少。我总结了五个高频翻车点都是血泪经验每条按现象、原因、解决来写希望能帮你少走弯路。5.1 现象卡在第一章的数学符号进度停滞现象翻开PDF第一页“定义 1.1”、Pr[]、E[]、i.i.d.以及各种不等式读了半小时书还在第一页。原因这份PDF是讲义默认读者已经学过概率论。它不是教材没有耐心从零教微积分。如果你把每个符号都查一遍再往下走等于在读一本字典。解决第一次阅读直接跳到跳跃表或随机化快速排序那里有具体的算法和证明。遇到看不懂的符号先猜含义或者查前面的定义不恋战。读完算法再回头补概率论。如果你连期望、独立性都忘光了花一天时间快速过一遍大学概率论笔记比硬啃PDF效率高得多。5.2 现象把“期望运行时间”当成“最坏运行时间”来理解现象看到“期望O(n log n)”就放心地在实时系统里使用结果偶尔一次运行时间突然飙到几十倍导致超时。原因期望不等于上界。随机算法的一小部分随机路径可能非常慢虽然概率低但在你不能容忍尾延迟的系统中必须考虑高概率边界。解决读PDF时对每个定理先问这里给的是期望界还是高概率界如果是期望界能否用切尔诺夫界推出更严格的高概率界在工程实现时对随机化快速排序、随机哈希表等要设置超时保护或者采用多算法冗余而不是盲目相信期望值。5.3 现象自己推导证明时乱用独立性假设现象在证明跳跃表某层节点数的期望时自己把“每个节点是否在第k层”当成独立事件算出错误的方差。原因节点的层高是独立抽取的但“在第k层出现”这个事件确实独立而“第k层节点数”是这些独立指示变量之和独立性成立。但在别的算法里比如随机收缩过程各条边是否被选中是相关的不能直接用独立乘积。解决每次使用“和的方差方差之和”前检查协方差是否为0。更稳妥的风格是在证明中写下“这些事件是独立的因为……”写不出来就改用并界或条件期望。这份PDF中的证明经常默认读者能看出独立性看不出就去翻概率论课本。5.4 现象随机算法在本地跑的结果不稳定怀疑程序写错了现象同一个输入运行五次得到五次不同的结果有时正确有时错误开始怀疑代码有bug。原因随机算法本身就有随机性输出或运行时间有波动是正常的。但你可能会把“算法正确性概率”和“实现bug”混淆。比如随机收缩算法单次运行很可能得不到最小割这不是bug而是重复次数不够。解决先固定随机种子复现结果确认逻辑一致性。然后用统计视角看待多跑几十次看结果的分布。如果是正确性概率问题就提高重复次数如果是运行时间波动就检查是否触发了最坏随机路径。这条“统计调试”习惯是读这份PDF之后最大的收获。5.5 现象把讲义当小说读不写代码看过就忘现象一个月前读过跳跃表那一章感觉懂了现在面试被问“层高为什么是几何分布”支支吾吾。原因讲义里的定理推导是“输入到输出”的路径你没有亲手构建这个路径。看证明就像看别人打游戏自己上场还是迷路。解决读每个算法的当天必须写一个最小实现并做一个对照实验。比如跳跃表你要亲眼看到插入一万个随机节点后的层级分布符合几何分布随机收缩算法你要看到重复次数增加时成功概率的上升趋势。这样做完你才算真正“拥有”了这个知识。看PDF不是目的能自己推、能自己写、能在项目里选型才是目的。6. 把这份PDF读成你的竞争力从习题到面试的一个具体训练套路如果你和我一样不是为了读PDF而读而是想把随机算法变成面试里的谈资、工程里的武器我给你一个可复制的训练套路三步消化法。以跳跃表为例。第一步读PDF里关于跳跃表的那一章先用纸笔推演“期望层高为什么是O(log n)”。别急着打开电脑推演过程能让你发现哪些符号没吃透。第二步写一个包含插入和查找的最小实现固定随机种子插入一万个随机key统计各层的节点数画出来看是否符合几何分布。第三步做一个随机数据下的性能对比实验分别用跳跃表和有序数组执行同样次数的查找记录耗时数据点。你会发现有序数组的二分查找虽然O(log n)但常数极小跳跃表常数较大但插入和删除更快。这个对比结论面试里能讲出层次。我自己以前偷懒跳跃表这种结构只看了结论就跳过结果有一次在模拟项目里需要频繁插入删除且有序遍历我用了数组加二分插入导致大量元素移动性能翻车。后来用这份PDF的方法把证明和代码一起过了一遍才明白跳跃表的价值不在单次查询而在“插入查找删除”的期望均衡。现在我的习惯是读完一个随机算法先写一个带随机种子的最小复现再做一次至少三组参数的对比实验然后才在真正项目里参考它。这套习惯帮我省了很多“以为会了”的后悔药。希望帮到你。本文还有配套的精品资源点击获取
