很多算法的分析都会从一句熟悉的话开始期望平均时间是 ……。这句话好用、干净也常常是真的。比如说随机快速排序的期望时间是 O(nlog⁡n)O(nlogn)哈希表一次查找的期望时间是 O(1)O(1)跳表的期望查找时间是 O(log⁡n)O(logn)。期望复杂度告诉我们一个涉及随机性的程序大概有多快给了一个不错的第一印象。但程序员写代码时面对的不是“平均宇宙”。一次请求、一次插入、一次排序任务都发生在某个具体时刻。期望复杂度没有告诉我们这一次会不会踩到很慢的分支也没有告诉我们慢分支发生的概率有多小。它只把所有可能的运行时间按概率加权压成一个数字。这就是高概率复杂度出现的地方。它不满足于说“平均下来不坏”而是试图回答一个更贴近工程直觉的问题坏事会不会频繁发生本文主要比较三种保证期望保证、高概率保证和最坏情况保证。它们回答的问题分别是平均快不快、绝大多数时候快不快、以及任何时候都快不快。保证类型典型形式含义期望复杂度E[X]O(f(n))E[X]O(f(n))平均运行时间不大高概率复杂度Pr⁡[X≤Cf(n)]≥1−1/ncPr[X≤Cf(n)]≥1−1/nc坏情况概率随规模增长迅速下降最坏情况复杂度对所有情况都有 XO(f(n))XO(f(n))没有例外路径理解期望复杂度设随机变量 XX 表示算法运行时间。如果我们证明 E[X]O(f(n))E[X]O(f(n))意思是对算法内部随机性取平均后运行时间的均值不超过某个常数倍的 f(n)f(n)。这里的随机性可能来自随机 pivot、随机哈希函数、随机层高也可能来自假设输入本身服从某个分布。期望是一个线性而温和的指标。它对分析者很友好因为 E[XY]E[X]E[Y]E[XY]E[X]E[Y]即使 XX 和 YY 不独立也成立。很多复杂算法能先做出期望分析靠的就是这个性质。以我们最熟悉的随机快速排序为例。令 CnCn​ 表示排序 nn 个不同元素时的比较次数。每一对元素是否被比较可以用指示变量表示。第 ii 小和第 jj 小的元素会被比较当且仅当在区间 [i,j][i,j] 内第一个被选为 pivot 的元素是它们之一因此概率是 2/(j−i1)2/(j−i1)。于是E[Cn]∑1≤ij≤n2j−i1O(nlog⁡n)E[Cn​]1≤ij≤n∑​j−i12​O(nlogn)这个推导很简单也很漂亮。它证明了平均比较次数很好但没有直接排除某次运行接近 n2n2 的可能。我们知道快速排序存在每一次都选到极端 pivot 的可能只是概率非常小。期望复杂度的问题不在于它错而在于它太会“原谅”低概率的大代价。一个随机变量可以大部分时候很小极少数时候巨大最后期望仍然可接受。反过来也可能出现期望不算差但尾部概率对工程系统已经不可接受。服务端延迟、内存峰值、批处理任务超时关心的往往不是均值而是某种尾部保证。如果某个算法以 1/n21/n2 的概率花费 O(n3)O(n3) 时间以 1−1/n21−1/n2 的概率花费 O(n)O(n) 时间那么它的期望时间仍然是 O(n)O(n)。但少数情况下它会花费远超正常路径的巨大时间。期望把这种风险摊薄了高概率复杂度则要求我们把这种风险单独拎出来看。理解高概率复杂度算法分析里常见的 “with high probability”通常缩写为 w.h.p.。一种较强的常用定义是对任意给定的常数 c0c0某个事件发生的概率至少为 1−1/nc1−1/nc。也有一些文章更宽松把失败概率为 1/nΩ(1)1/nΩ(1) 的保证称为高概率保证。写成形式就是Pr⁡[X≤Cf(n)]≥1−1ncPr[X≤Cf(n)]≥1−nc1​这里 CC 可以依赖于 cc但不能依赖于 nn。和 E[X]O(f(n))E[X]O(f(n)) 相比这个定义要求的是随着问题规模增大好情况的概率可以无限接近 1而坏情况的概率会迅速下降到接近 0。高概率保证仍然不是最坏情况保证。它仍然允许坏情况存在。差别在于坏情况被关进了一个概率足够小的角落。对很多随机化数据结构来说它比期望复杂度更加严格。即使不追求每条执行路径都漂亮我们也希望失败概率随规模增长迅速下降。这里有一个细微但重要的习惯高概率里的概率通常是关于算法内部随机性的而不是“用户输入刚好比较友善”的概率。比如随机快速排序面对任意固定输入只要 pivot 随机选它依然可以得到高概率界。这个区分会影响算法能不能抵抗恶意输入。分析概率复杂度的工具从期望复杂度到高概率复杂度中间缺的东西叫尾界。期望控制的是平均值尾界控制的是偏离平均值的概率。比如说概率论里有有名的 Markov 不等式对非负随机变量 XX有Pr⁡[X≥a]≤E[X]aPr[X≥a]≤aE[X]​如果一个算法是期望 O(f(n))O(f(n)) 的即 E[X]O(f(n))E[X]O(f(n))那么取 ancf(n)ancf(n)可以得到Pr⁡[X≥ncf(n)]≤O(1nc)Pr[X≥ncf(n)]≤O(nc1​)这确实是一个高概率陈述但界变成了 O(ncf(n))O(ncf(n))。这说明仅靠 Markov 不等式得到的结论通常太粗了它能把“期望小”变成“极大值不太常见”但很难直接证明“以高概率仍然是 O(f(n))O(f(n))”。要证明“以高概率仍然是 O(f(n))O(f(n))”通常需要更细的结构。常见路径有三种把运行时间拆成许多独立或弱相关的小随机变量然后用 Chernoff 界证明变量的变化幅度有限然后用 Azuma 或 McDiarmid 不等式或者直接分析递归和数据结构的形状再用 union bound 控制所有位置。Chernoff 界Chernoff 界是最常见的工具之一。设 X∑iXiX∑i​Xi​其中 XiXi​ 是独立的 0/10/1 随机变量μE[X]μE[X]。一个常用形式是当 0δ≤10δ≤1 时Pr⁡[X≤(1−δ)μ]≤exp⁡(−δ2μ2)Pr[X≤(1−δ)μ]≤exp(−2δ2μ​)以及Pr⁡[X≥(1δ)μ]≤exp⁡(−δ2μ3)Pr[X≥(1δ)μ]≤exp(−3δ2μ​)它比 Markov 强的地方在于偏离概率随 μμ 指数下降。当 μΘ(log⁡n)μΘ(logn) 时失败概率就能变成 n−Θ(1)n−Θ(1)。很多高概率复杂度证明的味道正是把问题改写成“在 Θ(log⁡n)Θ(logn) 次随机试验里成功次数不会太少”。Union bound把局部保证拼成全局保证高概率分析里有一个朴素但极常用的工具union bound。它说对任意事件 E1,…,EmE1​,…,Em​Pr⁡[⋃i1mEi]≤∑i1mPr⁡[Ei]Pr[i1⋃m​Ei​]≤i1∑m​Pr[Ei​]它不要求事件独立实际上是一种放缩。因此它非常适合把“单个元素失败概率很小”升级成“所有元素都不失败”。代价也很明显如果你要同时保证 mm 个对象都好每个对象的失败概率就要比 1/m1/m 更小。比如想得到全局失败概率 1/nc1/nc而对象数是 nn单个对象失败概率通常要压到 1/nc11/nc1。这就是很多证明里常数要“留余量”的原因。高概率复杂度里的常数并不只是装饰它经常承载了 union bound 的预算。随机快速排序不只是期望 O(nlog⁡n)O(nlogn)随机快速排序的期望复杂度很容易证明而高概率分析则进一步证明坏情况来自递归树过深如果每次 pivot 都极端深度会退化到 nn。但随机 pivot 不太可能一直极端。考虑某个元素沿着递归树向下走的路径。当前子数组大小为 mm。我们设定如果 pivot 落在中间一半的位置也就是 rank 介于 m/4m/4 和 3m/43m/4 之间那么无论这个元素被分到哪一边下一层子问题规模都至多是 3m/43m/4。称这样的 pivot 为一次好分裂。显然随机 pivot 是好分裂的概率至少为 1/21/2。如果一条路径上有 kk 次好分裂子问题规模变为至多 n(3/4)kn(3/4)k。当 k≥log⁡4/3nk≥log4/3​n 时规模降到常数。也就是说只要在前 tt 层里积累到足够多的好分裂这条路径就结束了。令 GG 表示前 tt 层中的好分裂次数。严格地说它不一定是一个独立二项变量因为每一步面对的子数组都依赖之前的随机选择。但在条件于过去的情况下下一次分裂为好分裂的概率仍然至少为 1/21/2。因此可以用 Chernoff 型尾界或者用被二项分布支配的方式来控制它。取 tclog⁡ntclogn当 cc 足够大时可以得到Pr⁡[Glog⁡4/3n]≤n−Ω(c)Pr[Glog4/3​n]≤n−Ω(c)这说明某个固定元素的递归深度超过 O(log⁡n)O(logn) 的概率是多项式级别地小。再对所有 nn 个元素做 union bound得到所有元素的递归深度都是 O(log⁡n)O(logn) 的概率至少为 1−1/nc1−1/nc只要常数选得足够大。一旦所有元素的递归深度都是 O(log⁡n)O(logn)比较次数也就容易控制了。每个元素只会和它所在递归路径上的 pivot 比较因此每个元素参与的比较次数是 O(log⁡n)O(logn)。把所有元素加起来总比较次数就是 O(nlog⁡n)O(nlogn)。因此随机快速排序不仅是期望 O(nlog⁡n)O(nlogn) 的同时也是高概率 O(nlog⁡n)O(nlogn) 的。这揭示出的事实是随机快速排序真正依赖的不是“平均 pivot 很好”而是“在较大规模数组上连续很多次 pivot 都很坏”的概率极低。跳表期望高度与最大高度跳表是另一种适合分析的结构。每个节点的层高通常由连续抛硬币决定节点先出现在第 11 层每次以概率 1/21/2 晋升到更高一层。于是某个节点高度至少为 kk 的概率是 2−(k−1)2−(k−1)。单个节点的期望高度是常数但跳表的性能不取决于单个节点而取决于整张表的最高层和搜索路径长度。最高层的高概率分析很直接。若有 nn 个节点则Pr⁡[存在高度至少为 k 的节点]≤n⋅2−(k−1)Pr[存在高度至少为 k 的节点]≤n⋅2−(k−1)这是 union bound。取 k(c2)log⁡2nk(c2)log2​n上式至多为 1/nc1/nc。所以跳表高度以高概率是 O(log⁡n)O(logn)。查找时从最高层开始水平移动直到再走会越过目标然后下降一层。每一层的水平移动次数可以看作由几何分布控制的随机量跨过太多节点意味着在一段区域内连续缺少更高层的“塔”这种事件的概率会指数下降。把各层加起来查找长度以高概率是 O(log⁡n)O(logn)。期望分析会说每层期望走常数步层数期望 O(log⁡n)O(logn)所以查找期望 O(log⁡n)O(logn)。高概率分析更进一步跳表不是只有平均路径短而是极高塔和极长路径本身都很难出现。在工程细节上最大层数通常也不会无限增长而是预先设置一个上限比如 3232 或 6464。这会把理论上的随机高度截断。对常见规模来说这没有问题但如果元素数量可能远超设计范围最高层不够会让查找退化。另一个细节是层高生成方式如果用随机整数的低位连续零个数生成高度要确认随机数低位质量足够好。跳表这一节的结论是随机层高不仅让平均搜索路径短也让整张表出现极高塔或极长路径的概率很低。哈希表期望 O(1)O(1) 与尾部陷阱哈希表经常被说成查找、插入、删除都是 O(1)O(1)。如果要更准确地说在简单均匀哈希假设下元素数量不超过容量时固定一次查找的期望成本是 O(1)O(1)如果扩容按倍数进行插入仍是均摊期望 O(1)O(1)。但是如果更进一步问两个问题呢第一个问题是固定一个 key它所在桶的长度是否通常很小第二个问题是整张表所有桶的最大长度是否都很小前者关系到单次操作的期望成本后者关系到是否能说“所有操作都高概率快”。把 nn 个 key 放进 nn 个桶。对某个固定桶负载的期望是 11。用 Chernoff 界可以证明它超过 O(log⁡n)O(logn) 的概率很小。但如果问最大桶长经典的 balls into bins 结论是最大负载大约为Θ(log⁡nlog⁡log⁡n)Θ(loglognlogn​)而不是 O(1)O(1)。也就是说即使哈希函数完全随机普通链式哈希也只能自然地给出期望 O(1)O(1) 的单次查找成本而不能保证所有桶都以高概率保持常数长度。这说明不同承诺的粒度不同。固定 key 的查找成本期望为 O(1)O(1)如果允许 O(log⁡n)O(logn) 或更精细的尾界也可以得到高概率上界。但“任意 key、任意时刻、所有桶都很大概率保持常数长度”不能由普通哈希表保证需要更强的数据结构设计。在普通哈希的基础上进行扩展用 cuckoo hashing、perfect hashing 或 treeified bucket可以得到不同形式的尾部或最坏情况保证。哈希表这一节的结论是日常所说的 O(1)O(1)很多时候更接近期望承诺而不是全局高概率承诺。从重试算法看期望的另一面还有一类算法的期望分析看起来非常轻松随机重试直到成功。假设每次尝试成功概率为 pp且相互独立。尝试次数 TT 服从几何分布期望是E[T]1pE[T]p1​如果 pp 是常数那期望尝试次数就是 O(1)O(1)。但“期望常数次尝试后成功”并不等于“最多常数次尝试后成功”。几何分布的尾部是Pr⁡[Tk](1−p)kPr[Tk](1−p)k如果希望失败概率降到 1/nc1/nc需要令 kΘ(log⁡n)kΘ(logn)。所以这类算法期望 O(1)O(1) 次尝试后成功而以高概率在 O(log⁡n)O(logn) 次尝试内成功。这个差别在实现里很实在。你不能只写一个无限循环然后说期望会停而是通常需要设置重试上限、超时和降级路径。理论上O(log⁡n)O(logn) 次重试换来 1−1/nc1−1/nc 的成功概率工程上重试次数还受到延迟预算、外部依赖成本和故障相关性的限制。独立性一旦不成立几何尾界也会失真。总结期望复杂度回答的是“平均成本是多少”高概率复杂度回答的是“坏情况有多罕见”。从工程角度看后者往往更接近我们真正关心的问题延迟是否会偶尔爆炸内存是否会偶尔冲高任务是否会偶尔超时。证明高概率复杂度的关键通常不是重新计算均值而是获得尾界。Chernoff 界控制独立随机变量和的偏离Azuma 和 McDiarmid 不等式控制有限变化的随机过程union bound 则把局部保证拼成全局保证。它们共同完成了一件事把“平均不错”升级为“绝大多数时候都不错”。因此当我们看到一个随机化算法声称期望很快时还应该继续追问几个问题尾部有多厚失败概率能否随 nn 多项式下降这个概率是针对算法内部随机性还是针对输入分布它能否抵抗恶意输入这些问题才是从“平均宇宙”走向真实系统的关键。