薄雾之上的上界：高概率复杂度的分析

很多算法的分析都会从一句熟悉的话开始：期望（平均）时间是 ……。这句话好用、干净，也常常是真的。

比如说，随机快速排序的期望时间是 $O(n \log n)$，哈希表一次查找的期望时间是 $O(1)$，跳表的期望查找时间是 $O(\log n)$。期望复杂度告诉我们，一个涉及随机性的程序大概有多快，给了一个不错的第一印象。

但程序员写代码时面对的不是“平均宇宙”。一次请求、一次插入、一次排序任务，都发生在某个具体时刻。期望复杂度没有告诉我们这一次会不会踩到很慢的分支，也没有告诉我们慢分支发生的概率有多小。它只把所有可能的运行时间按概率加权，压成一个数字。这就是高概率复杂度出现的地方。它不满足于说“平均下来不坏”，而是试图回答一个更贴近工程直觉的问题：坏事会不会频繁发生？

本文主要比较三种保证：期望保证、高概率保证和最坏情况保证。它们回答的问题分别是：平均快不快、绝大多数时候快不快、以及任何时候都快不快。

保证类型	典型形式	含义
期望复杂度	$\mathbb{E}[X] = O(f(n))$	平均运行时间不大
高概率复杂度	$\Pr[X \le C f(n)] \ge 1 - 1/n^c$	坏情况概率随规模增长迅速下降
最坏情况复杂度	对所有情况都有 $X = O(f(n))$	没有例外路径

理解期望复杂度

设随机变量 $X$ 表示算法运行时间。如果我们证明 $\mathbb{E}[X] = O(f(n))$，意思是对算法内部随机性取平均后，运行时间的均值不超过某个常数倍的 $f(n)$。这里的随机性可能来自随机 pivot、随机哈希函数、随机层高，也可能来自假设输入本身服从某个分布。

期望是一个线性而温和的指标。它对分析者很友好，因为 $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$，即使 $X$ 和 $Y$ 不独立也成立。很多复杂算法能先做出期望分析，靠的就是这个性质。

以我们最熟悉的随机快速排序为例。令 $C_n$ 表示排序 $n$ 个不同元素时的比较次数。每一对元素是否被比较，可以用指示变量表示。第 $i$ 小和第 $j$ 小的元素会被比较，当且仅当在区间 $[i,j]$ 内第一个被选为 pivot 的元素是它们之一，因此概率是 $2/(j-i+1)$。于是

$$\mathbb{E}[C_n] = \sum_{1 \le i < j \le n} \frac{2}{j-i+1} = O(n \log n)$$

这个推导很简单也很漂亮。它证明了平均比较次数很好，但没有直接排除某次运行接近 $n^2$ 的可能。我们知道，快速排序存在每一次都选到极端 pivot 的可能，只是概率非常小。

期望复杂度的问题不在于它错，而在于它太会“原谅”低概率的大代价。一个随机变量可以大部分时候很小，极少数时候巨大，最后期望仍然可接受。反过来也可能出现期望不算差，但尾部概率对工程系统已经不可接受。服务端延迟、内存峰值、批处理任务超时，关心的往往不是均值，而是某种尾部保证。

如果某个算法以 $1/n^2$ 的概率花费 $O(n^3)$ 时间，以 $1-1/n^2$ 的概率花费 $O(n)$ 时间，那么它的期望时间仍然是 $O(n)$。但少数情况下，它会花费远超正常路径的巨大时间。期望把这种风险摊薄了，高概率复杂度则要求我们把这种风险单独拎出来看。

理解高概率复杂度

算法分析里常见的 “with high probability”，通常缩写为 w.h.p.。一种较强的常用定义是：对任意给定的常数 $c > 0$，某个事件发生的概率至少为 $1 - 1/n^c$。也有一些文章更宽松，把失败概率为 $1/n^{\Omega(1)}$ 的保证称为高概率保证。

写成形式就是

$$\Pr[X \le C f(n)] \ge 1 - \frac{1}{n^c}$$

这里 $C$ 可以依赖于 $c$，但不能依赖于 $n$。和 $\mathbb{E}[X] = O(f(n))$ 相比，这个定义要求的是：随着问题规模增大，好情况的概率可以无限接近 1，而坏情况的概率会迅速下降到接近 0。

高概率保证仍然不是最坏情况保证。它仍然允许坏情况存在。差别在于，坏情况被关进了一个概率足够小的角落。对很多随机化数据结构来说，它比期望复杂度更加严格。即使不追求每条执行路径都漂亮，我们也希望失败概率随规模增长迅速下降。

这里有一个细微但重要的习惯：高概率里的概率通常是关于算法内部随机性的，而不是“用户输入刚好比较友善”的概率。比如随机快速排序面对任意固定输入，只要 pivot 随机选，它依然可以得到高概率界。这个区分会影响算法能不能抵抗恶意输入。

分析概率复杂度的工具

从期望复杂度到高概率复杂度，中间缺的东西叫尾界。期望控制的是平均值，尾界控制的是偏离平均值的概率。比如说，概率论里有有名的 Markov 不等式：对非负随机变量 $X$，有

$$\Pr[X \ge a] \le \frac{\mathbb{E}[X]}{a}$$

如果一个算法是期望 $O(f(n))$ 的，即 $\mathbb{E}[X] = O(f(n))$，那么取 $a = n^c f(n)$，可以得到

$$\Pr[X \ge n^c f(n)] \le O\left(\frac{1}{n^c}\right)$$

这确实是一个高概率陈述，但界变成了 $O(n^c f(n))$。这说明仅靠 Markov 不等式得到的结论通常太粗了：它能把“期望小”变成“极大值不太常见”，但很难直接证明“以高概率仍然是 $O(f(n))$”。

要证明“以高概率仍然是 $O(f(n))$”，通常需要更细的结构。常见路径有三种：把运行时间拆成许多独立或弱相关的小随机变量，然后用 Chernoff 界；证明变量的变化幅度有限，然后用 Azuma 或 McDiarmid 不等式；或者直接分析递归和数据结构的形状，再用 union bound 控制所有位置。

Chernoff 界

Chernoff 界是最常见的工具之一。设 $X = \sum_i X_i$，其中 $X_i$ 是独立的 $0/1$ 随机变量，$\mu = \mathbb{E}[X]$。一个常用形式是：当 $0 < \delta \le 1$ 时，

$$\Pr[X \le (1-\delta)\mu] \le \exp\left(-\frac{\delta^2 \mu}{2}\right)$$

以及

$$\Pr[X \ge (1+\delta)\mu] \le \exp\left(-\frac{\delta^2 \mu}{3}\right)$$

它比 Markov 强的地方在于，偏离概率随 $\mu$ 指数下降。当 $\mu = \Theta(\log n)$ 时，失败概率就能变成 $n^{-\Theta(1)}$。很多高概率复杂度证明的味道，正是把问题改写成“在 $\Theta(\log n)$ 次随机试验里，成功次数不会太少”。

Union bound：把局部保证拼成全局保证

高概率分析里有一个朴素但极常用的工具：union bound。它说对任意事件 $E_1,\dots,E_m$，

$$\Pr\left[\bigcup_{i=1}^m E_i\right] \le \sum_{i=1}^m \Pr[E_i]$$

它不要求事件独立，实际上是一种放缩。因此它非常适合把“单个元素失败概率很小”升级成“所有元素都不失败”。代价也很明显：如果你要同时保证 $m$ 个对象都好，每个对象的失败概率就要比 $1/m$ 更小。比如想得到全局失败概率 $1/n^c$，而对象数是 $n$，单个对象失败概率通常要压到 $1/n^{c+1}$。这就是很多证明里常数要“留余量”的原因。高概率复杂度里的常数并不只是装饰，它经常承载了 union bound 的预算。

随机快速排序：不只是期望 $O(n \log n)$

随机快速排序的期望复杂度很容易证明，而高概率分析则进一步证明：坏情况来自递归树过深；如果每次 pivot 都极端，深度会退化到 $n$。但随机 pivot 不太可能一直极端。

考虑某个元素沿着递归树向下走的路径。当前子数组大小为 $m$。我们设定，如果 pivot 落在中间一半的位置，也就是 rank 介于 $m/4$ 和 $3m/4$ 之间，那么无论这个元素被分到哪一边，下一层子问题规模都至多是 $3m/4$。称这样的 pivot 为一次好分裂。显然随机 pivot 是好分裂的概率至少为 $1/2$。

如果一条路径上有 $k$ 次好分裂，子问题规模变为至多 $n(3/4)^k$。当 $k \ge \log_{4/3} n$ 时，规模降到常数。也就是说，只要在前 $t$ 层里积累到足够多的好分裂，这条路径就结束了。

令 $G$ 表示前 $t$ 层中的好分裂次数。严格地说，它不一定是一个独立二项变量，因为每一步面对的子数组都依赖之前的随机选择。但在条件于过去的情况下，下一次分裂为好分裂的概率仍然至少为 $1/2$。因此可以用 Chernoff 型尾界，或者用被二项分布支配的方式来控制它。

取 $t = c \log n$，当 $c$ 足够大时，可以得到

$$\Pr[G < \log_{4/3} n] \le n^{-\Omega(c)}$$

这说明某个固定元素的递归深度超过 $O(\log n)$ 的概率是多项式级别地小。再对所有 $n$ 个元素做 union bound，得到所有元素的递归深度都是 $O(\log n)$ 的概率至少为 $1 - 1/n^c$，只要常数选得足够大。

一旦所有元素的递归深度都是 $O(\log n)$，比较次数也就容易控制了。每个元素只会和它所在递归路径上的 pivot 比较，因此每个元素参与的比较次数是 $O(\log n)$。把所有元素加起来，总比较次数就是 $O(n \log n)$。因此，随机快速排序不仅是期望 $O(n \log n)$ 的，同时也是高概率 $O(n \log n)$ 的。

这揭示出的事实是：随机快速排序真正依赖的不是“平均 pivot 很好”，而是“在较大规模数组上，连续很多次 pivot 都很坏”的概率极低。

跳表：期望高度与最大高度

跳表是另一种适合分析的结构。每个节点的层高通常由连续抛硬币决定：节点先出现在第 $1$ 层，每次以概率 $1/2$ 晋升到更高一层。于是某个节点高度至少为 $k$ 的概率是 $2^{-(k-1)}$。

单个节点的期望高度是常数，但跳表的性能不取决于单个节点，而取决于整张表的最高层和搜索路径长度。最高层的高概率分析很直接。若有 $n$ 个节点，则

$$\Pr[\text{存在高度至少为 } k \text{ 的节点}] \le n \cdot 2^{-(k-1)}$$

这是 union bound。取 $k = (c+2)\log_2 n$，上式至多为 $1/n^c$。所以跳表高度以高概率是 $O(\log n)$。

查找时从最高层开始，水平移动直到再走会越过目标，然后下降一层。每一层的水平移动次数可以看作由几何分布控制的随机量；跨过太多节点意味着在一段区域内连续缺少更高层的“塔”，这种事件的概率会指数下降。把各层加起来，查找长度以高概率是 $O(\log n)$。

期望分析会说：每层期望走常数步，层数期望 $O(\log n)$，所以查找期望 $O(\log n)$。高概率分析更进一步：跳表不是只有平均路径短，而是极高塔和极长路径本身都很难出现。

在工程细节上，最大层数通常也不会无限增长，而是预先设置一个上限，比如 $32$ 或 $64$。这会把理论上的随机高度截断。对常见规模来说这没有问题，但如果元素数量可能远超设计范围，最高层不够会让查找退化。另一个细节是层高生成方式：如果用随机整数的低位连续零个数生成高度，要确认随机数低位质量足够好。

跳表这一节的结论是：随机层高不仅让平均搜索路径短，也让整张表出现极高塔或极长路径的概率很低。

哈希表：期望 $O(1)$ 与尾部陷阱

哈希表经常被说成查找、插入、删除都是 $O(1)$。如果要更准确地说，在简单均匀哈希假设下，元素数量不超过容量时，固定一次查找的期望成本是 $O(1)$；如果扩容按倍数进行，插入仍是均摊期望 $O(1)$。

但是如果更进一步问两个问题呢？第一个问题是：固定一个 key，它所在桶的长度是否通常很小？第二个问题是：整张表所有桶的最大长度是否都很小？前者关系到单次操作的期望成本，后者关系到是否能说“所有操作都高概率快”。

把 $n$ 个 key 放进 $n$ 个桶。对某个固定桶，负载的期望是 $1$。用 Chernoff 界可以证明它超过 $O(\log n)$ 的概率很小。但如果问最大桶长，经典的 balls into bins 结论是最大负载大约为

$$\Theta\left(\frac{\log n}{\log \log n}\right)$$

而不是 $O(1)$。也就是说，即使哈希函数完全随机，普通链式哈希也只能自然地给出期望 $O(1)$ 的单次查找成本，而不能保证所有桶都以高概率保持常数长度。

这说明不同承诺的粒度不同。固定 key 的查找成本期望为 $O(1)$；如果允许 $O(\log n)$ 或更精细的尾界，也可以得到高概率上界。但“任意 key、任意时刻、所有桶都很大概率保持常数长度”不能由普通哈希表保证，需要更强的数据结构设计。在普通哈希的基础上进行扩展，用 cuckoo hashing、perfect hashing 或 treeified bucket，可以得到不同形式的尾部或最坏情况保证。

哈希表这一节的结论是：日常所说的 $O(1)$，很多时候更接近期望承诺，而不是全局高概率承诺。

从重试算法看期望的另一面

还有一类算法的期望分析看起来非常轻松：随机重试直到成功。假设每次尝试成功概率为 $p$，且相互独立。尝试次数 $T$ 服从几何分布，期望是

$$\mathbb{E}[T] = \frac{1}{p}$$

如果 $p$ 是常数，那期望尝试次数就是 $O(1)$。

但“期望常数次尝试后成功”并不等于“最多常数次尝试后成功”。几何分布的尾部是

$$\Pr[T > k] = (1-p)^k$$

如果希望失败概率降到 $1/n^c$，需要令 $k = \Theta(\log n)$。所以这类算法期望 $O(1)$ 次尝试后成功，而以高概率在 $O(\log n)$ 次尝试内成功。

这个差别在实现里很实在。你不能只写一个无限循环然后说期望会停，而是通常需要设置重试上限、超时和降级路径。理论上，$O(\log n)$ 次重试换来 $1 - 1/n^c$ 的成功概率；工程上，重试次数还受到延迟预算、外部依赖成本和故障相关性的限制。独立性一旦不成立，几何尾界也会失真。

总结

期望复杂度回答的是“平均成本是多少”，高概率复杂度回答的是“坏情况有多罕见”。从工程角度看，后者往往更接近我们真正关心的问题：延迟是否会偶尔爆炸，内存是否会偶尔冲高，任务是否会偶尔超时。

证明高概率复杂度的关键通常不是重新计算均值，而是获得尾界。Chernoff 界控制独立随机变量和的偏离，Azuma 和 McDiarmid 不等式控制有限变化的随机过程，union bound 则把局部保证拼成全局保证。它们共同完成了一件事：把“平均不错”升级为“绝大多数时候都不错”。

因此，当我们看到一个随机化算法声称期望很快时，还应该继续追问几个问题：尾部有多厚？失败概率能否随 $n$ 多项式下降？这个概率是针对算法内部随机性，还是针对输入分布？它能否抵抗恶意输入？这些问题，才是从“平均宇宙”走向真实系统的关键。