简介：这份PDF是Sariel Har-Peled所著《随机算法》的讲义稿，面向已具备算法基础与证明能力的学习者，用于系统理解随机化思想如何突破确定性算法的效率与下界限制。内容从快速排序与二叉空间分割切入，围绕三个硬币博弈、对手论证、去随机化、随机化与平均情况分析的差异，以及样本空间、σ-代数、概率测度、随机变量与条件概率等基本概率工具展开，兼顾理论直觉与形式化定义。资源包共1个文件，为PDF格式，整体约8.78MB，单册即可覆盖课程主线，便于按章节顺序阅读或配合每周作业练习。目前已有115人学习，适合算法课程进阶、竞赛准备及研究入门者作为参考读物，帮助建立对随机算法适用场景与局限性的整体认识。
1. 随机算法到底在“随机”什么：从抛硬币说起
你有没有遇到过这种情况：同样一段代码，跑两次结果不一样，第一次秒出答案，第二次却卡了半天？很多人第一反应是“有 bug”，但有一类算法，它天生就带着这种“看运气”的脾气，这就是随机算法。通俗地说，随机算法就是在执行过程中主动做随机决策的算法——它会在关键步骤抛一次“硬币”，根据结果决定下一步往哪走。这个硬币不是装饰，而是算法设计的一部分。它值得搞懂，是因为很多问题用确定性方法要么慢得离谱，要么根本写不出来，而引入随机性之后，答案反而来得又快又简单。接下来就把这个概念一层层拆开，看看它为什么成立、和哪些说法容易混、什么时候该用。
2. 为什么要在算法里“掷骰子”：随机性带来的三重好处
2.1 速度：随机化能把最坏情况“摊平”
确定性算法有一个绕不开的软肋：只要存在一个让算法表现最差的输入，对手就能拿它做文章。随机算法换了个思路——它不保证每一次都快，但保证“平均来看”很快，而且这个平均不是对输入做假设，是对算法自己的随机选择做平均。
以快速排序为例。确定性快排如果每次都选到最小或最大元素当枢轴，就会退化成平方级时间，这是经典的血泪教训。随机化快排的做法很简单：每次从待排序元素里均匀随机挑一个当枢轴。这一挑，就把“对手可以精心构造最坏输入”这条路堵死了。书里给出的结论是：对 n 个元素排序，随机快排的期望比较次数不超过 n + 2n ln n，而且这个界对所有输入都成立，不需要对输入分布做任何假设。
用一段伪代码看这个“随机”落在哪：
import random def randomized_quicksort(arr): if len(arr) <= 1: return arr # 关键一步：枢轴不是取第一个，而是随机挑一个 pivot_index = random.randrange(len(arr)) pivot = arr[pivot_index] # 按枢轴分成小于和大于两部分 less = [x for i, x in enumerate(arr) if x < pivot or (x == pivot and i < pivot_index)] greater = [x for i, x in enumerate(arr) if x > pivot or (x == pivot and i > pivot_index)] return randomized_quicksort(less) + [pivot] + randomized_quicksort(greater)这里的random.randrange(len(arr))就是随机决策点。参数上唯一要关注的是随机源的均匀性——只要每个位置被选中的概率相等，期望复杂度的推导就成立。如果随机源有偏，理论上界会打折扣，但实践中普通伪随机数生成器足够用。失败时看什么？如果发现某次运行特别慢，先别怀疑算法，检查输入里是否有大量重复元素，那会影响划分的平衡性，这属于实现细节而非随机化本身的问题。
2.2 简洁：随机版本往往比确定性版本更好写
有些问题，确定性算法不是不存在，而是写起来极其繁琐。随机算法经常能用几行代码达到同样的效果，代价只是接受一个可控的出错概率。
书里讲了一个验证两个二进制向量是否相等的例子。你只能通过一个黑盒计算两个向量的模 2 点积，想判断 v 和 u 是否相等。确定性做法要把每个分量都读出来比对，调用次数多。随机做法是：随机生成一个 0/1 向量 r，分别算 v 和 u 与 r 的点积，比较两个结果。如果 v 等于 u，两个点积必然相等；如果 v 不等于 u，两个点积不相等的概率至少是一半。也就是说，一次比较有一半概率抓出“不相等”，重复 t 次，漏判的概率降到 1/2 的 t 次方。
import random def vectors_equal(v, u, trials=30): # 每次独立生成随机向量 r，做模2点积比对 for _ in range(trials): r = [random.randint(0, 1) for _ in range(len(v))] dot_v = sum(a * b for a, b in zip(v, r)) % 2 dot_u = sum(a * b for a, b in zip(u, r)) % 2 if dot_v != dot_u: return False # 一旦不等，铁定不相等 return True # 多次都没抓出差异，判定相等（有小概率错）trials就是放大次数，取 30 时漏判概率约十亿分之一。注意这个算法的错误是单边的：说“不相等”一定对，说“相等”才可能错。这种“错也只往一个方向错”的性质，是后面区分算法类型的关键线索。
2.3 破局：有些问题确定性算法根本做不到
最让人服气的理由是：存在一些问题，已知的确定性算法要么不存在，要么慢到没有实用价值，而随机算法能干净利落地解决。
书里那个三硬币游戏就是典型。对手把三枚硬币放在等边三角形三个顶点上，每步你可以要求翻转某几枚硬币，翻完如果三枚都朝上就赢，否则对手可以把棋盘旋转 0 度、120 度或 -120 度。随机策略是每步随机选一枚硬币翻。因为任意时刻总有两枚朝上、一枚朝下，随机选有三分之一概率正好选中那枚“孤立”的，游戏终止所需的步数服从几何分布，期望只要 3 步，超过 i 步的概率是 (2/3) 的 i 次方，衰减很快。而确定性策略呢？对手可以模拟你的算法，提前知道你要翻哪枚，然后旋转棋盘让你永远翻不到正确组合。这里随机性不是锦上添花，而是唯一出路。
3. 随机算法和“平均情况分析”不是一回事：一个常被搞混的分界
3.1 随机性在算法里，不在输入里
这是初学者最容易踩的坑。平均情况分析假设输入本身服从某个概率分布，然后问“在这个分布下算法表现如何”。随机算法完全不假设输入是随机的——输入可以是任意刁钻的数据，随机性来自算法内部的那次掷骰子。
打个比方：平均情况分析像是“假设今天路况按某种规律分布，估算通勤时间”；随机算法像是“不管路况怎样，我出门前随机选一条路线，保证平均不堵”。前者赌的是外部环境，后者赌的是自己的选择。书里明确点出，随机算法的分析更具普适性，因为它对输入没有要求；而平均情况分析很难找到真正反映现实世界的输入分布，很多分布下揭示的结构在真实数据里根本不存在。
3.2 期望运行时间不等于“有时会很慢就没事”
有人会问：随机快排最坏情况还是平方级，那和确定性快排有什么区别？区别在于“最坏情况出现的条件”。确定性快排的最坏情况可以被特定输入稳定触发，对手构造一次你就中招。随机快排要触发平方级，需要随机源连续多次都挑到极端枢轴，这个概率随 n 增大迅速趋近于零。书里还提到，类似的界不仅在期望中成立，在很大概率下也成立。也就是说，随机算法的“慢”是一个概率极低的事件，而不是一个可以被稳定利用的漏洞。
3.3 随机源是前提，不是细节
所有随机算法的分析都建立在“能访问一个均匀随机源”这个假设上。书里在讲快排时专门声明：假设可以均匀生成 1 到 n 之间的随机数。这个假设在理论分析里是干净的，在工程里则要留意伪随机数的质量。如果随机源有周期性或偏差，那些“概率极低”的坏事件可能变得不那么低。这不是让你去手搓随机数生成器，而是提醒：随机算法的性能保证，和随机源的质量是绑定的。
4. 拉斯维加斯与蒙特卡洛：两种“随机”脾气要分清
4.1 一个保正确、一个保速度
随机算法内部还要再分两类，这是书里第 2.4 节的核心区分，也是面试和考试里高频的易混点。
拉斯维加斯算法：永远返回正确结果，随机性只影响运行时间。随机快排就是代表——排出来的顺序一定对，只是这次跑得快下次跑得慢。它的“代价”体现在时间上，不体现在答案上。
蒙特卡洛算法：运行时间是固定的（通常是多项式级），但结果可能出错，出错概率可以通过重复执行来压低。前面那个向量相等验证就是蒙特卡洛：说“不相等”一定对，说“相等”有小概率错，多跑几次把错误率压下去。
用一句话记：拉斯维加斯赌的是时间，蒙特卡洛赌的是正确性。
4.2 复杂度类里的位置：RP、ZPP、BPP 各自管什么
书里顺带把随机算法的复杂度类梳理了一遍，理解这几个缩写能帮你把概念钉死。
RP 类：最坏情况多项式时间，且错误是单边的——输入属于语言时以至少 1/2 概率接受，不属于时一定拒绝。也就是“只可能把‘是’误判成‘否’的方向出错”（按书里定义，接受概率在属于时至少一半，不属于时为零）。前面向量验证就落在这个框架里。
co-RP：RP 的补类，错误方向反过来。一个问题如果同时属于 RP 和 co-RP，就存在一个不出错的算法，也就是拉斯维加斯算法。
ZPP：零错误概率多项式时间，正是拉斯维加斯算法对应的类——期望多项式时间，答案永远对。
BPP：有界错误概率多项式时间，双边都可能错，但正确概率至少 3/4，可以通过重复执行放大到接近 1。
PP 类则是个“看起来像但不好用”的类：只要求正确概率略大于 1/2，可以任意接近一半，导致无法有效放大，所以实用价值有限。这个细节说明一个道理：随机算法的“随机”不是随便给个概率就行，错误率必须留出可放大的余量，否则重复多少次都救不回来。
4.3 常见误区清单
易混点一：把“随机算法”当成“结果随机的算法”。实际上随机算法追求的是确定性的正确答案（拉斯维加斯）或可控错误率的答案（蒙特卡洛），随机只是手段，不是目的。区分方法：看它是否对正确性有承诺。
易混点二：把“期望 O(n log n)”理解成“每次都是 O(n log n)”。期望是多次运行的平均，单次可能偏离。区分方法：看结论里有没有“以很大概率”这个补充，书里对快排就补了这句。
易混点三：把蒙特卡洛的“可能出错”和“不可靠”划等号。蒙特卡洛的错误率是可以算出来、可以压下去的，重复 t 次错误率指数下降。区分方法：看有没有明确的错误概率上界和放大手段。
易混点四：以为随机算法一定比确定性算法快。书里说得很清楚：即使不更快，随机算法通常也更简单。速度、简洁、破局是三件不同的事，不要混成一件。
5. 什么时候该用随机算法，什么时候别用
5.1 适合用的场景
第一类是对抗性环境或最坏输入可被构造的场景。只要你的算法会被“有心人”针对，随机化就是一道保险。书里对手论证那段说得很直白：确定性算法完全可预测，对手比算法更强；随机化让算法不可预测，把博弈拉回平衡。
第二类是问题本身确定性解法过于复杂或未知的场景。三硬币游戏那种“确定性策略根本赢不了”的情况，随机是唯一解。工程里更常见的是近似和验证类任务，比如大规模数据的一致性校验，用随机采样验证比逐项比对划算得多。
第三类是对简洁性要求高的场景。随机算法往往几行代码就能达到确定性算法几十行的效果，维护成本低。书里向量验证和矩阵乘法验证（用随机向量把矩阵乘法验证降到 O(n²)）都是这个思路。
5.2 不适合用的场景
对正确性零容忍、且无法接受任何概率性错误的场景，别用蒙特卡洛。比如涉及不可逆操作的决策，错一次代价极大，这时候要么用拉斯维加斯型算法（保正确只赌时间），要么老老实实上确定性方案。
随机源不可靠或不可控的场景也要谨慎。随机算法的性能保证依赖均匀随机源，如果运行环境里随机数质量存疑，那些理论上的“极低概率坏事件”可能不再极低。
还有一类容易被忽略：问题规模很小、确定性算法本来就够快的场景。给一个 n=10 的排序上随机快排，收益几乎为零，反而多了一层理解成本。随机算法的价值随问题规模和最坏情况的严重程度上升，小问题上不必为了“时髦”而随机。
5.3 一个判断流程
拿到一个问题，我会按这个顺序过一遍：先问确定性算法是否存在且够快，是则直接用；再问最坏输入是否可被稳定构造，是则考虑随机化摊平；然后问能否接受概率性错误，能接受就用蒙特卡洛加重复放大，不能接受就找拉斯维加斯型方案；最后确认随机源质量是否撑得住理论保证。这套流程不是玄学，是把书里那几个概念落到判断上的顺序。
提示：判断一个随机算法靠不靠谱，先看它的错误是单边还是双边，再看错误率能不能通过重复执行指数级压低。两个都满足，基本可以放心用。
从那以后我每次遇到“这个算法偶尔特别慢”的问题，都会先强制走一遍“随机性在算法里还是在输入里”的区分，再决定是改随机源还是换算法类型。希望帮到你。这份资料把随机算法的定义、快排与 BSP 的期望分析、验证恒等式的随机方法、最近点对的线性期望算法，以及拉斯维加斯与蒙特卡洛的复杂度类划分串成了一条线，适合想把这个概念从“听过”读到“讲得清”的人顺着看下去。
本文还有配套的精品资源，点击获取
