4 Randomized and Others

Randomized Algorithms 随机化算法¶

随机化算法（randomized algorithm）在运行过程中使用随机数。随机性可以帮助算法避免固定的最坏输入，也可以在空间或时间受限时给出近似结果。

Monte Carlo 与 Las Vegas¶

随机化算法通常分为两类：

Monte Carlo 算法：运行时间有确定上界，但答案的正确性或质量带有概率保证。算法可能给出错误答案，或者以较高概率得到高质量答案。
Las Vegas 算法：答案始终正确，但运行时间具有随机性，通常分析其期望运行时间。

例如，随机化 QuickSort 始终输出正确的排序结果，但随机 pivot 会使运行时间随机，平均运行时间为 $O(n\log n)$，因此属于 Las Vegas 算法。

如果数组中一半元素为 a、一半元素为 b，随机抽取位置寻找 a，则一次抽取成功的概率为 $1/2$，期望尝试次数为 $2$。这个例子说明，算法可以用随机性换取较短的期望搜索时间。

随机排列与随机抽样¶

Fisher–Yates Shuffle¶

要使数组的所有排列等概率出现，可以使用 Fisher–Yates shuffle：

Java
static void shuffle(int[] array) {
    for (int i = array.length; i > 0; i--) {
        int j = random.nextInt(i);
        swap(array, i - 1, j);
    }
}

第 $i$ 轮从尚未确定的位置 $0,\ldots,i-1$ 中均匀选择一个位置，与位置 $i-1$ 交换。第一个位置有 $n$ 种选择，第二个位置有 $n-1$ 种选择，依此类推，因此每个排列出现的概率都是

\[ \frac1n\cdot\frac1{n-1}\cdots\frac11=\frac1{n!}. \]

下面的写法看似也在不断交换随机位置，但不能产生均匀随机排列：

Java
static void shuffle(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int j = random.nextInt(array.length);
        swap(array, i, j);
    }
}

它有 $n^n$ 种随机选择序列，但只有 $n!$ 个排列，且不同排列对应的选择序列数量不相同。例如 $n=3$ 时，某些排列出现 $5/27$，另一些只出现 $4/27$，因此排列并不等概率。

均匀选择 $m$ 个位置¶

从长度为 $n$ 的数组中选择恰好 $m$ 个不同位置时，反复随机抽取并在重复时重来，会在 $m$ 接近 $n$ 时产生较多重复尝试。

Knuth 给出了一次扫描算法：处理位置 $i=0,1,\ldots,n-1$ 时，剩余需要选择 $m$ 个位置，剩余位置总数为 $n-i$。以概率 $m/(n-i)$ 选择当前位置：

Text Only
1 2 3 4 5	`generate(m, n): for i = 0, 1, ..., n - 1: if random() % (n - i) < m: output i m = m - 1`

每次选择的概率正好等于“剩余需要选择的位置数”除以“剩余位置总数”，因此最终得到的每个 $m$-子集等概率出现。算法只扫描一次，时间复杂度为 $O(n)$，额外空间复杂度可以做到 $O(1)$（不计输出）。

StupidSort 与随机运行时间¶

考虑如下算法：

Java
void stupidSort(int[] array) {
    while (!sorted(array)) {
        shuffle(array);
    }
}

假设数组元素互不相同，则 $n!$ 个排列中只有一个是有序排列。若 shuffle 能均匀生成排列，则每次洗牌成功的概率为 $1/n!$，直到成功所需的洗牌次数服从几何分布，其期望为 $n!$。

检查数组是否有序需要 $O(n)$ 时间，Fisher–Yates shuffle 也需要 $O(n)$ 时间。因此期望运行时间为

\[ O(n\cdot n!)=O((n+1)!). \]

这是期望运行时间，而不是每次运行都有的确定上界。极端情况下，算法可能连续很多次洗牌都没有成功。

随机化局部改进¶

随机化也可以用来探索组合优化问题的解空间。例如在 $0$-1 背包问题（0-1 knapsack problem）中，可以：

先用贪心算法得到一个可行解；
随机从当前背包中移除一个物品；
尝试用其他物品补充容量，可以再次使用贪心规则；
如果新解更好则保留，否则恢复原解。

这类随机局部搜索通常能改善解的质量，但若没有额外证明，不能自动得到最优解或固定近似比。

Karger Minimum Cut Karger 最小割算法¶

问题定义¶

给定无向连通多重图（multigraph）

\[G=(V,E),\]

将顶点划分为两个非空集合 $V_1,V_2$，使跨越两个集合的边数最少。这样的边集合称为割（cut），最小割的大小记为 $\lambda$。

等价地，最小割是删除尽可能少的边后使图变得不连通所需的边集合。

随机收缩算法¶

Karger 算法重复执行以下步骤，直到只剩两个超顶点：

从当前图中均匀随机选择一条边 $(x,y)$；
将 $x$ 和 $y$ 收缩为一个超顶点；
保留重边，删除自环；
剩下的两个超顶点代表一个候选割。

如果算法在收缩过程中从未选中某个最小割 $C$ 中的边，那么最后得到的候选割恰好就是 $C$。如果收缩了 $C$ 中的边，$C$ 就会被破坏。

单次运行保留最小割的概率¶

设当前有 $r$ 个超顶点，并固定一个大小为 $\lambda$ 的最小割 $C$。每个超顶点的度数至少为 $\lambda$，因此

\[ |E|=\frac12\sum_{v\in V}\deg(v)\ge \frac{r\lambda}{2}. \]

随机选中的边属于 $C$ 的概率至多为

\[ \Pr[e\in C]\le \frac{\lambda}{|E|}\le \frac2r. \]

因此，在有 $r$ 个超顶点时安全收缩的概率至少为

\[ 1-\frac2r=\frac{r-2}{r}. \]

从 $n$ 个顶点收缩到 $2$ 个顶点的过程中，保留 $C$ 的概率至少为

\[ \begin{aligned} \Pr[\text{保留 }C] &\ge \prod_{r=3}^{n}\left(1-\frac2r\right)\\ &=\frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdots\frac13\\ &=\frac{2}{n(n-1)}. \end{aligned} \]

因此单次运行找到某个固定最小割的概率为 $\Omega(1/n^2)$，失败概率至多为

\[ 1-\frac{2}{n(n-1)}\le 1-\frac2{n^2}. \]

重复运行¶

独立运行 $k$ 次并保留其中最小的割。单次运行失败概率至多为 $1-2/n^2$，因此总失败概率至多为

\[ \left(1-\frac2{n^2}\right)^k \le e^{-2k/n^2}. \]

当 $k=cn^2$ 时，失败概率至多为 $e^{-2c}$；若希望失败概率不超过 $\delta$，取

\[ k\ge \frac{n^2}{2}\ln\frac1\delta \]

即可。于是重复 $\Theta(n^2\log(1/\delta))$ 次可以把成功概率提高到至少 $1-\delta$。

Streaming Algorithms 流式算法¶

流式算法（streaming algorithm）按顺序处理不断到达的数据项。数据项经过后通常不能再次读取，而算法只能使用远小于输入规模的存储空间，因此往往只能近似回答查询。

典型查询包括：

不同元素的数量；
哪些元素至少出现过两次；
数据流的频率、频率矩或其他统计量。

流式算法的典型应用包括：

外部存储算法：数据主要存放在磁盘或网络存储中，顺序扫描通常比随机访问更高效；
通信复杂度与 sketching：用短摘要交换大数据集的信息；
低空间算法：使用次线性空间处理无法完整装入内存的数据；
次线性时间算法与压缩感知。

示例：寻找缺失数字¶

整数 $1,2,\ldots,n$ 以任意顺序到达，其中恰好缺少一个整数。可以利用异或运算的性质

\[ x\oplus x=0,\qquad x\oplus 0=x. \]

算法先计算 $1\oplus2\oplus\cdots\oplus n$，再依次与每个到达的数字异或：

Text Only
1 2 3 4 5 6	`missing = 0 for i = 1, 2, ..., n: missing = missing XOR i for each arriving x: missing = missing XOR x return missing`

每个出现的数字会被异或两次而抵消，最后只剩缺失数字。算法只需一次扫描，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$，并且不会产生整数求和溢出问题。

Amortized Analysis 摊还分析¶

摊还分析（amortized analysis）研究一个数据结构执行一串操作时的总成本，而不是只看某一次操作的最坏成本。

它与概率分析不同：

概率分析通常固定一个算法，考察所有可能输入上的平均运行时间；若使用概率分布，则得到期望运行时间；
摊还分析不需要概率。它对任意操作序列给出总成本保证，即使序列中包含昂贵操作，也可以把成本平均到整段序列上。

若任意包含 $n$ 次操作的序列总成本为 $O(n)$，则称每次操作的摊还成本为 $O(1)$。

摊还分析有三种经典方法：

聚合法（aggregate analysis）：直接界定整段序列的总成本；
记账法（accounting method）：给不同操作分配不同摊还成本，并把多收的部分保存为 credit；
势能法（potential method）：把预付成本保存为整个数据结构的势能。

栈操作的摊还分析¶

考虑栈操作：

PUSH(S, x)：将元素压入栈，实际成本为 $1$；
POP(S)：弹出栈顶元素，实际成本为 $1$；
MULTIPOP(S, k)：最多弹出 $k$ 个元素，实际成本为 $\min(s,k)$，其中 $s$ 是当前栈大小。

Text Only
1 2 3 4	`MULTIPOP(S, k): while S is not empty and k > 0: POP(S) k = k - 1`

单次 MULTIPOP 可能需要 $O(n)$ 时间。若只使用单次最坏成本相加，$n$ 次操作的上界会被估计为 $O(n^2)$，但这个界并不紧。

聚合法¶

从空栈开始，某个元素只有在先被 PUSH 后才可能被 POP，而每个被压入的元素最多被弹出一次。因此在包含 $n$ 次操作的序列中：

\[ \#\text{POP}\le \#\text{PUSH}\le n. \]

所有 PUSH、POP 和 MULTIPOP 的总实际成本为 $O(n)$，所以平均每次操作的摊还成本为

\[ \frac{O(n)}n=O(1). \]

二进制计数器的聚合法¶

设二进制计数器有 $k$ 位，数组 $A[0\ldots k-1]$ 中 $A[0]$ 是最低位。INCREMENT 从最低位开始，把连续的 $1$ 置为 $0$，再把遇到的第一个 $0$ 置为 $1$：

Text Only
1 2 3 4 5 6 7	`INCREMENT(A): i = 0 while i < k and A[i] == 1: A[i] = 0 i = i + 1 if i < k: A[i] = 1`

一次 INCREMENT 最坏可能翻转 $k$ 位，因此直接分析会得到 $O(k)$ 的单次成本和 $O(nk)$ 的 $n$ 次成本。但不同位的翻转频率不同：

第 $0$ 位每次翻转，最多翻转 $n$ 次；
第 $1$ 位每两次翻转一次，最多翻转 $\lfloor n/2\rfloor$ 次；
第 $2$ 位每四次翻转一次，最多翻转 $\lfloor n/4\rfloor$ 次；
一般地，第 $i$ 位最多翻转 $\lfloor n/2^i\rfloor$ 次。

因此总翻转次数小于

\[ \sum_{i=0}^{k-1}\left\lfloor\frac{n}{2^i}\right\rfloor <n\sum_{i=0}^{\infty}\frac1{2^i}=2n. \]

连续执行 $n$ 次 INCREMENT 的总成本为 $O(n)$，每次操作的摊还成本为 $O(1)$。

记账法¶

记账法为不同类型的操作分配不同的摊还成本。若某次操作的摊还成本高于实际成本，多出的部分保存为 credit；之后实际成本较高的操作可以使用这些 credit。

设第 $i$ 次操作的实际成本为 $c_i$，摊还成本为 $\widehat c_i$。必须保证对任意前缀 $t$ 都有

\[ \sum_{i=1}^{t}\widehat c_i \ge \sum_{i=1}^{t}c_i. \]

等价地，任意时刻累计 credit 都不能为负。这样，所有操作的总摊还成本就是总实际成本的上界。

栈的记账法¶

分配如下摊还成本：

PUSH：$2$；
POP：$0$；
MULTIPOP：$0$。

每次 PUSH 的 $2$ 个单位成本中，$1$ 个支付当前压栈操作，另 $1$ 个作为 credit 保存在被压入的元素上。元素被 POP 或 MULTIPOP 弹出时，使用该元素上的 credit 支付弹出成本。

因此每次操作的摊还成本至多为 $2$，包含 $n$ 次操作的序列总摊还成本为 $O(n)$，实际总成本也为 $O(n)$。

二进制计数器的记账法¶

把每一位翻转的实际成本设为 $1$。每当某一位从 $0$ 置为 $1$ 时，收取摊还成本 $2$：其中 $1$ 个单位支付本次置位，另 $1$ 个单位保存在该位上。

当该位之后从 $1$ 复位为 $0$ 时，使用保存在该位上的 credit 支付复位成本。每次 INCREMENT 至多把一位从 $0$ 置为 $1$，所以每次操作的摊还成本至多为 $2$，$n$ 次操作总成本为 $O(n)$。

势能法¶

势能法（potential method）把预付成本保存为整个数据结构的势能，而不是绑定到某个具体对象上。

设初始数据结构为 $D_0$，执行 $n$ 次操作后依次得到 $D_1,\ldots,D_n$。第 $i$ 次操作的实际成本为 $c_i$，势能函数为

\[ \Phi(D_i)\in\mathbb R. \]

通常令 $\Phi(D_0)=0$，并要求对任意 $i$ 都有 $\Phi(D_i)\ge0$。第 $i$ 次操作的摊还成本定义为

\[ \widehat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1}). \]

对前 $n$ 次操作求和：

\[ \begin{aligned} \sum_{i=1}^{n}\widehat c_i &=\sum_{i=1}^{n}\left(c_i+\Phi(D_i)-\Phi(D_{i-1})\right)\\ &=\sum_{i=1}^{n}c_i+\Phi(D_n)-\Phi(D_0). \end{aligned} \]

因为 $\Phi(D_n)\ge\Phi(D_0)=0$，总摊还成本不小于总实际成本。

势能增加时，摊还成本高于当前实际成本，相当于预先储存能量；势能减少时，摊还成本可以低于实际成本，由之前保存的势能补足差额。

栈的势能法¶

取栈中元素个数作为势能：

\[ \Phi(S)=|S|. \]

若当前栈大小为 $s$：

PUSH：实际成本为 $1$，势能变化为 $+1$，所以

$$\widehat c=1+1=2.$$

POP：实际成本为 $1$，势能变化为 $-1$，所以

$$\widehat c=1-1=0.$$

MULTIPOP(S,k)：令 $k'=\min(s,k)$，实际成本为 $k'$，势能变化为 $-k'$，所以

$$\widehat c=k'-k'=0.$$

每次操作的摊还成本均为 $O(1)$，因此任意 $n$ 次栈操作的总成本为 $O(n)$。

二进制计数器的势能法¶

取计数器中 $1$ 的个数作为势能：

\[ \Phi(D_i)=b_i, \]

其中 $b_i$ 是第 $i$ 次操作后计数器中 $1$ 的数量。

设第 $i$ 次操作复位了 $t_i$ 位。若该操作还把一位置为 $1$，则实际成本至多为 $t_i+1$，并且

\[ b_i\le b_{i-1}-t_i+1. \]

所以势能变化满足

\[ \Phi(D_i)-\Phi(D_{i-1})le 1-t_i. \]

于是摊还成本为

\[ \begin{aligned} \widehat c_i &=c_i+\Phi(D_i)-\Phi(D_{i-1})\\ &\le (t_i+1)+(1-t_i)\\ &=2. \end{aligned} \]

因此 $n$ 次 INCREMENT 的总实际成本为 $O(n)$。

Smoothed Analysis 平滑分析¶

平滑分析（smoothed analysis）研究一个输入在受到轻微随机扰动后，算法的期望性能。它位于最坏情况分析与平均情况分析之间：

最坏情况分析直接寻找最不利输入；
平均情况分析假设输入来自指定分布；
平滑分析从任意固定输入出发，加入幅度较小的随机扰动，再分析扰动后的期望运行时间。

平滑分析通常需要更深入的概率工具，用来解释一些最坏情况下很慢、但在轻微噪声下通常表现良好的算法。

小结¶

随机化算法：Monte Carlo 固定运行时间但正确性带概率，Las Vegas 保证答案正确但运行时间随机；
随机排列：Fisher–Yates 在每一步缩小可选范围，能够均匀生成所有排列；
Karger 最小割：单次成功概率为 $\Omega(1/n^2)$，重复运行可以把失败概率降到任意给定的 $\delta$；
流式算法：在有限空间中一次处理数据流，通常用近似方式回答查询；
摊还分析：不使用概率，而是从整个操作序列的总成本出发分析平均性能；
三种方法：聚合法直接界定总成本，记账法保存 credit，势能法把预付成本记录为数据结构的势能；
平滑分析：通过轻微随机扰动研究算法在现实输入附近的平均表现。