算法设计-03：分治算法

分治思想

分治（divide and conquer）把原问题拆成若干个同类型、规模更小的子问题，递归求解，再把子问题的答案合并。分析这类算法时，需要同时看子问题的个数、每个子问题的规模，以及拆分和合并的代价。后文的整数乘法、归并排序、选择算法和矩阵乘法都遵循这一思路。

快速整数乘法

上一讲的竖式乘法需要 $O(n^2)$ 位操作。提高速度的关键是减少递归乘法次数；常数次加减法通常只需 $O(n)$ 时间。

高斯的复数乘法技巧给出了一个直观例子。通常计算

$$(a+bi)(c+di)=(ac-bd)+(ad+bc)i$$

要做四次实数乘法。令 $P=ac$、$Q=bd$、$R=(a+b)(c+d)$，则 $ad+bc=R-P-Q$，于是只用三次乘法即可完成。单次运算只省了一个乘法；若在每层递归中都省去一个乘法，渐近复杂度就会改变。

设 $x,y$ 都不超过 $n$ 位。为方便均分，先在高位补零，使 $n$ 成为 2 的幂；新的位数 $n'$ 满足 $n\le n'<2n$，因此不影响渐近复杂度。把两个数按高、低各 $n/2$ 位拆开：

$$x=2^{n/2}x_L+x_R, \qquad y=2^{n/2}y_L+y_R.$$

直接展开有

$$xy=2^n x_Ly_L+2^{n/2}(x_Ly_R+x_Ry_L)+x_Ry_R.$$

若四个乘积分别递归计算，拆分、移位、加法合计为 $O(n)$，则

$$T(n)=4T(n/2)+O(n)=O(n^2).$$

这与竖式乘法同阶。模仿高斯的技巧，只计算三个乘积：

$$P_1=x_Ly_L, \qquad P_2=x_Ry_R, \qquad P_3=(x_L+x_R)(y_L+y_R).$$

因为 $P_3-P_1-P_2=x_Ly_R+x_Ry_L$，可在 $O(n)$ 的加减和移位后得到

$$xy=2^nP_1+2^{n/2}(P_3-P_1-P_2)+P_2.$$

用上一讲的 $11\times13$ 验算一次：$11=1011_2$、$13=1101_2$，按两位拆开得到 $x_L=2,x_R=3,y_L=3,y_R=1$。于是 $P_1=6$、$P_2=3$、$P_3=(2+3)(3+1)=20$，合并结果为 $16\cdot6+4\cdot(20-6-3)+3=143$。这与竖式及 Al-Khwarizmi 乘法的结果一致。

Karatsuba 乘法的伪代码如下。为使任意长度都能直接递归实现，令 $m=\lceil n/2\rceil$，以最低 $m$ 位为右半部分；当 $n$ 为偶数时，这与上面的均分完全一致。$x_L+x_R$ 或 $y_L+y_R$ 至多比半长多一位，子问题规模仍为 $n/2+O(1)$，不改变最终渐近界。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MULTIPLY}(x,y) \\[4pt] \hline \textbf{输入：}\ \text{两个非负二进制整数 }x,y \\ n=\max\{\text{两数的位数}\},\quad m=\lceil n/2\rceil \\ \textbf{if}\ n\le4\ \textbf{then}\ \text{return}\ xy \\ (x_L,x_R)=\text{把 }x\text{ 按高位、低 }m\text{ 位拆分} \\ (y_L,y_R)=\text{把 }y\text{ 按高位、低 }m\text{ 位拆分} \\ P_1=\text{MULTIPLY}(x_L,y_L) \\ P_2=\text{MULTIPLY}(x_R,y_R) \\ P_3=\text{MULTIPLY}(x_L+x_R,y_L+y_R) \\ \text{return}\ 2^{2m}P_1+2^m(P_3-P_1-P_2)+P_2 \\ \hline \end{array}&& \end{aligned}$$

正确性由上面的展开式和 $P_3-P_1-P_2$ 的恒等式直接得到。另一种等价写法是计算 $x_Ly_L$、$x_Ry_R$、$(x_L-x_R)(y_L-y_R)$，再利用

$$x_Ly_R+x_Ry_L=x_Ly_L+x_Ry_R-(x_L-x_R)(y_L-y_R).$$

负的中间数可以带符号计算。讲义用这两种三乘法写法说明：Kolmogorov 曾猜想竖式乘法已是最优，Karatsuba 在 1960 年给出了反例。

忽略取整和相加时多出的一位，递归式写成 $T(n)=3T(n/2)+O(n)$；上述适用于任意位数的实现对应 $T(n)\le3T(\lceil n/2\rceil+1)+O(n)$，渐近解相同。在递归树的第 $k$ 层，有 $3^k$ 个规模约为 $n/2^k$ 的子问题；该层合并代价为

$$3^k O\!\left(\frac{n}{2^k}\right) =O\!\left(n\left(\frac32\right)^k\right).$$

树高为 $\log_2n$。各层代价以 $3/2$ 的比率增长，末层代价约为 $3^{\log_2n}=n^{\log_23}$；整个几何级数与末层同阶，所以

$$T(n)=\Theta\!\left(n^{\log_23}\right) \approx\Theta(n^{1.585}).$$

课件提问：能否进一步改进乘法？

可以。三次半规模乘法已经突破 $O(n^2)$，课件还指出存在更快的整数乘法算法；本讲不展开这些后续方法。

主定理

对于等规模子问题，课件给出的主定理处理

$$T(n)=aT(\lceil n/b\rceil)+O(n^d), \qquad a>0,\ b>1,\ d\ge0,$$

其中 $a$ 是子问题数，$b$ 是规模缩小的倍数，$O(n^d)$ 是本层拆分与合并的上界。假设基例代价为 $O(1)$，则

$$T(n)= \begin{cases} O(n^d), & d>\log_ba,\\ O(n^d\log n), & d=\log_ba,\\ O(n^{\log_ba}), & d<\log_ba. \end{cases}$$

若本层代价实际为 $\Theta(n^d)$，并满足通常的正代价条件，相应的界也可写成 $\Theta$。应用前应先检查子问题是否等比例缩小；只有形式相似还不足以套用该定理。

证明可先假设 $n$ 是 $b$ 的整数次幂。递归树高 $\log_bn$；第 $k$ 层有 $a^k$ 个规模为 $n/b^k$ 的子问题，因此该层工作量为

$$a^kO\!\left(\frac{n}{b^k}\right)^d =O(n^d)\left(\frac{a}{b^d}\right)^k.$$

层代价构成公比 $a/b^d$ 的几何级数：

• $a/b^d<1$，总代价由顶层主导，为 $O(n^d)$；
• $a/b^d=1$，每层同阶，共 $O(\log n)$ 层，为 $O(n^d\log n)$；
• $a/b^d>1$，总代价由末层主导，为 $O(a^{\log_bn})=O(n^{\log_ba})$。

例如 Karatsuba 乘法中 $a=3,b=2,d=1$，属于第三种情形。上一讲的普通四递归乘法有 $a=4,b=2,d=1$，得到 $O(n^2)$。

不等规模递推

当各子问题按不同的比例缩小，主定理通常不能直接使用。课件给出 Akra-Bazzi 定理：若

$$T(n)=\sum_{i=1}^{k}a_iT(b_in+h_i(n))+g(n),$$

其中 $a_i>0$、$0<b_i<1$，扰动项满足 $|h_i(n)|=O(n/\log^2n)$，$g(n)$ 满足定理要求的多项式增长等条件。令 $p$ 为下式的解：

$$\sum_{i=1}^{k}a_ib_i^p=1.$$

则在这些条件下

$$T(n)=\Theta\!\left( n^p\left(1+\int_1^n\frac{g(u)}{u^{p+1}}\,\mathrm du\right) \right).$$

课件中的例子为

$$T(n)=T\!\left(\left\lfloor\frac n5\right\rfloor\right) +T\!\left(n-3\left\lfloor\frac n{10}\right\rfloor\right) +\frac{11}{5}n, \qquad T(0)=T(1)=0.$$

课件只写出 $T(0)=T(1)=0$。若把递推式用于 $2\le n<10$，第二项仍是 $T(n)$，所以这些基例不足以定义递推。下述渐近分析应理解为：递推式仅对足够大的 $n$ 使用，并为更小的规模另行指定有限的基例。

两个主比例分别是 $b_1=1/5$、$b_2=7/10$。取

$$h_1(n)=\left\lfloor\frac n5\right\rfloor-\frac n5, \qquad h_2(n)=\frac{3n}{10}-3\left\lfloor\frac n{10}\right\rfloor,$$

两者都为 $O(1)$。方程 $(1/5)^p+(7/10)^p=1$ 的解约为 $p=0.83978<1$。因为 $g(u)=11u/5$，

$$n^p\left(1+\int_1^n\frac{11u/5}{u^{p+1}}\,\mathrm du\right) =n^p\left(1+\frac{11}{5(1-p)}(n^{1-p}-1)\right) =\Theta(n).$$

故该递推的解为 $T(n)=\Theta(n)$。这里也能看出，两个子问题的规模之和小于 $n$，而每层另有线性工作。

Quiz：求递推 $T(n)=4T(\sqrt n)+1$ 的渐近解。

解答：补充常数规模的基例后，设 $m=\log_2n$，定义 $S(m)=T(2^m)$。因为 $\sqrt{2^m}=2^{m/2}$，原式变成

$$S(m)=4S(m/2)+1.$$

对新变量 $m$ 应用主定理，$a=4,b=2,d=0$，所以 $S(m)=\Theta(m^{\log_24})=\Theta(m^2)$。代回得到

$$\boxed{T(n)=\Theta((\log n)^2)}.$$

也可从递归树验证：输入规模经过 $k$ 层变为 $n^{1/2^k}$，约 $\log_2\log n$ 层后到达常数；末层约有 $4^{\log_2\log_2n}=(\log_2n)^2$ 个结点。此题不能直接把 $\sqrt n$ 当成 $n/b$ 套原变量上的主定理；先作对数换元才得到等比例递推。

归并排序

归并排序把长度为 $n$ 的数组切成左右两半，递归排序，再合并两个已排序的数组。合并时比较两侧当前的首元素，取较小者放入结果；若某一侧为空，就把另一侧剩余元素接到末尾。使用 $\le$ 时，相等元素优先取原数组靠左的一侧，递归版本可保持稳定排序。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MERGE}(x[1\ldots k],y[1\ldots l]) \\[4pt] \hline \textbf{if}\ k=0\ \textbf{then}\ \text{return}\ y \\ \textbf{if}\ l=0\ \textbf{then}\ \text{return}\ x \\ \textbf{if}\ x[1]\le y[1]\ \textbf{then} \\ \qquad \text{return}\ x[1]\circ\text{MERGE}(x[2\ldots k],y) \\ \textbf{else}\ \text{return}\ y[1]\circ\text{MERGE}(x,y[2\ldots l]) \\ \hline \end{array}&& \end{aligned}$$

这里 $\circ$ 表示把一个元素接到序列前端。两个输入序列已有序，较小的首元素必是并集中的最小元素；删除它后同样的性质继续成立。归纳可得 MERGE 正确。每次比较至少移走一个元素，合并总代价为 $O(k+l)$。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MERGESORT}(a[1\ldots n]) \\[4pt] \hline \textbf{if}\ n\le1\ \textbf{then}\ \text{return}\ a \\ m=\lfloor n/2\rfloor \\ x=\text{MERGESORT}(a[1\ldots m]) \\ y=\text{MERGESORT}(a[m+1\ldots n]) \\ \text{return}\ \text{MERGE}(x,y) \\ \hline \end{array}&& \end{aligned}$$

两半在递归结束后分别有序，而 MERGE 正确地合并且不丢失元素，因此 MERGESORT 正确。时间递推为 $T(n)=2T(n/2)+O(n)$，主定理的第二种情形给出 $O(n\log n)$；合并各层的比较也达到同阶，故为 $\Theta(n\log n)$。标准数组实现通常需要 $O(n)$ 额外空间。

例如 $[5,1,4,2]$ 先分为 $[5,1]$、$[4,2]$，分别排序成 $[1,5]$、$[2,4]$；最后依次取较小的首元素，得到 $[1,2,4,5]$。每一层都只对已排序的两段执行线性合并。

练习 2.14：给定一个含 $n$ 个元素的数组，其中一些元素重复出现。设计 $O(n\log n)$ 时间的算法，删除重复项，使每个不同元素只保留一次。

本题考查排序后的相等元素连续性，以及排序后线性扫描的应用。

先用归并排序将数组 $A[1\ldots n]$ 按非递减顺序排列。相同元素必然连续出现，因此只需保留每段相同元素中的一个。

若 $n=0$，返回空数组。否则令 $w=1$，依次扫描 $i=2,\ldots,n$：若 $A[i]\ne A[w]$，则令 $w\leftarrow w+1$，再令 $A[w]\leftarrow A[i]$。最后返回前缀 $A[1\ldots w]$。

伪代码如下。数组下标从 $1$ 开始，MERGESORT 返回非递减排序后的数组。

// 排序后原地压缩重复段，返回每个不同取值的一份副本。
function REMOVE-DUPLICATES(A):
    n ← length(A)
    if n = 0:
        return []
    A ← MERGESORT(A)
    w ← 1
    for i ← 2 to n:
        if A[i] ≠ A[w]:
            w ← w + 1
            A[w] ← A[i]
    return A[1..w]

处理完原数组的前 $i$ 个元素后，前缀 $A[1\ldots w]$ 恰好包含这些元素的所有不同取值，且每个取值只保留一次：若当前值与最后保留的值相同，跳过它；否则追加这个新值。由归纳法可知最终结果正确。写入位置不超过当前扫描位置，不会覆盖尚未扫描的元素。

排序需要 $O(n\log n)$ 时间，扫描需要 $O(n)$ 时间，因此

$$T(n)=O(n\log n)+O(n)=O(n\log n).$$

课件还给出队列版本：先把每个元素作为长度为 1 的有序序列入队；反复从队首取出两个序列，合并后放到队尾；队列只剩一个序列时返回。若 $n=0$，直接返回空序列。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：ITERATIVE-MERGESORT}(a[1\ldots n]) \\[4pt] \hline \textbf{if}\ n=0\ \textbf{then}\ \text{return}\ [\ ] \\ Q=\text{空队列} \\ \textbf{for}\ i=1\ \textbf{to}\ n\ \textbf{do}\ \text{INJECT}(Q,[a[i]]) \\ \textbf{while}\ |Q|>1\ \textbf{do} \\ \qquad x=\text{EJECT}(Q),\ y=\text{EJECT}(Q) \\ \qquad \text{INJECT}(Q,\text{MERGE}(x,y)) \\ \text{return}\ \text{EJECT}(Q) \\ \hline \end{array}&& \end{aligned}$$

INJECT 表示队尾入队，EJECT 表示队首出队。队列中的每个序列始终有序，且全部序列恰好组成原始元素的一个划分，因此最终序列有序并包含所有输入。先进先出的合并顺序使各元素经历 $O(\log n)$ 次合并，总时间仍为 $O(n\log n)$。这个队列版本在 $n$ 不是 2 的幂时可能改变相等元素的原始相对顺序；若要求稳定性，可使用前述按原数组相邻区间合并的递归版本。

练习 2.19：给定 $k$ 个有序数组，每个数组有 $n$ 个元素，要将它们归并成一个包含 $kn$ 个元素的有序数组。

本题考查归并代价、求和分析和平衡分治。

(a) 先归并前两个数组，再依次合入第三、第四个数组，直到全部合并。用 $k,n$ 表示该算法的时间复杂度。

记输入数组为 $L[1],\ldots,L[k]$，其中 $k\ge1$，MERGE 表示线性时间的二路归并。该策略可形式化为：

// 依次把下一个有序数组归并进累计结果。
function SEQUENTIAL-MERGE(L[1..k]):
    R ← L[1]
    for j ← 2 to k:
        R ← MERGE(R, L[j])
    return R

合入第 $j$ 个数组时，已有结果长 $(j-1)n$，新数组长 $n$，本次归并需要 $\Theta(jn)$ 时间。对 $k\ge2$，

$$T(k,n)=\sum_{j=2}^{k}\Theta(jn) =\Theta\!\left(n\left(\frac{k(k+1)}2-1\right)\right) =\Theta(nk^2).$$

(b) 用分治给出一个更高效的算法。

将 $k$ 个数组分成数量尽量相等的两组，递归将每组归并成一个有序数组，再归并两个结果。只剩一个数组时直接返回。

记输入数组为 $L[1],\ldots,L[k]$，MERGE 为线性二路归并。初始调用 MERGE-K$(L,1,k)$：

// 平衡划分数组编号区间 [left, right]，归并该区间的所有数组。
function MERGE-K(L, left, right):
    if left = right:
        return L[left]
    middle ← floor((left + right) / 2)
    X ← MERGE-K(L, left, middle)
    Y ← MERGE-K(L, middle + 1, right)
    return MERGE(X, Y)

递归返回的两个数组均有序，且分别恰好包含对应组的所有元素；归并后仍有序且不丢失元素，因此算法由归纳法保证正确。

若 $k$ 是 $2$ 的幂，

$$T(k,n)=2T(k/2,n)+\Theta(kn)=\Theta(kn\log k).$$

一般的 $k$ 可以补空数组到最近的 $2$ 的幂。每层处理至多 $kn$ 个元素，共 $\lceil\log_2k\rceil$ 层，所以同样得到 $O(kn\log k)$ 时间；平衡归并的总工作量为 $\Theta(kn\log k)$。当 $k=1$ 时直接返回原数组。

课件提问：归并排序还能更快吗？

若仅靠两两比较区分任意不同的输入元素，在最坏情况下不能突破 $\Omega(n\log n)$ 次比较。归并排序因此达到了比较排序的渐近最优界。

证明用决策树：每次比较只有两种结果，比较排序可表示成一棵二叉树。$n$ 个互异元素有 $n!$ 种排列，算法必须区分所有排列，因此树至少有 $n!$ 个叶子。若树高为 $h$，至多有 $2^h$ 个叶子，故

$$2^h\ge n!, \qquad h\ge\log_2(n!)=\Omega(n\log n),$$

最后一步可由 Stirling 公式得到。这个下界限定于比较模型；若输入具有额外结构，其他排序方法可以使用不同的操作。

课件的三元素决策树需要区分 $3!=6$ 种排列；高度为 2 的二叉树最多只有 4 个叶子，因此最坏情况下至少需要 $\lceil\log_2 6\rceil=3$ 次比较。

随机选择

中位数用于给一组数选出典型值。课件约定：若序列长度为偶数，取排序后靠左的那个中间元素，即第 $\lceil n/2\rceil$ 小的数。先排序再取中位数需要 $O(n\log n)$ 时间；若只求某个排名的元素，可以直接做选择：输入序列 $S$ 和 $1\le k\le|S|$，返回第 $k$ 小元素。

选取主元 $v\in S$，一次扫描把元素分成 $S_L$（小于 $v$）、$S_v$（等于 $v$）和 $S_R$（大于 $v$）。把等于 $v$ 的元素单列，能正确处理重复值。选择的递推规则为

$$\operatorname{selection}(S,k)= \begin{cases} \operatorname{selection}(S_L,k), & k\le|S_L|,\\ v, & |S_L|<k\le|S_L|+|S_v|,\\ \operatorname{selection}(S_R,k-|S_L|-|S_v|), & k>|S_L|+|S_v|. \end{cases}$$

分区后只需递归进入包含目标排名的那一侧，不必同时求解两侧。若主元始终接近中位数，递推 $T(n)=T(n/2)+O(n)=O(n)$；但选择主元本身不能依赖先求出中位数。课件采用从当前序列中均匀随机选取主元的方法。

例如 $S=[7,2,9,2,5,11,4]$、$k=4$。若抽中主元 $v=5$，则 $S_L=[2,2,4]$、$S_v=[5]$、$S_R=[7,9,11]$。因为 $|S_L|=3<4\le4=|S_L|+|S_v|$，可直接返回第 4 小的元素 $5$；两个相等的 $2$ 均留在左侧，不会影响排名判断。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：SELECTION}(S,k) \\[4pt] \hline \textbf{输入：}\ |S|\ge1,\ 1\le k\le|S| \\ v=\text{从 }S\text{ 中均匀随机选出的元素} \\ S_L=\{x\in S:x<v\},\ S_v=\{x\in S:x=v\},\ S_R=\{x\in S:x>v\} \\ \textbf{if}\ k\le|S_L|\ \textbf{then}\ \text{return}\ \text{SELECTION}(S_L,k) \\ \textbf{if}\ k\le|S_L|+|S_v|\ \textbf{then}\ \text{return}\ v \\ \text{return}\ \text{SELECTION}(S_R,k-|S_L|-|S_v|) \\ \hline \end{array}&& \end{aligned}$$

每次分区为 $O(n)$。最坏情况下，主元总落在端点附近，规模每轮只减少 1，需 $n+(n-1)+\cdots+1=\Theta(n^2)$ 时间。

期望时间却是 $O(n)$。把排名位于当前序列第 25% 到 75% 之间的主元称为好主元。随机取一个元素时，选到好主元的概率至少约 $1/2$；选到后，下一轮至多保留 $3n/4$ 个元素，重复值只会使缩减更快。类似抛公平硬币直到首次正面，期望次数 $E$ 满足

$$E=1+\frac12E, \qquad E=2.$$

因此在当前规模不超过 $n$ 的阶段，平均只需常数次分区就能得到一次至少 $1/4$ 的规模缩减。随后各阶段规模至多为 $3n/4,(3/4)^2n,\ldots$；把每阶段期望的扫描代价相加，得到

$$\mathbb E[T(n)] \le O(n)\sum_{j\ge0}\left(\frac34\right)^j =O(n).$$

这也解释了课件所写的期望递推 $T(n)\lesssim T(3n/4)+O(n)$：$3n/4$ 是一次好分区后的规模，失败分区的额外扫描已计入期望常数。算法总能返回正确答案，但运行时间随随机主元变化。

课件提问：求中位数需要先排序吗？

不需要。调用 $\operatorname{SELECTION}(S,\lceil n/2\rceil)$，可在期望 $O(n)$ 时间得到课件约定的中位数。

练习 2.22：给定两个长度分别为 $m,n$ 的有序表，设计 $O(\log m+\log n)$ 时间的算法，求两表合并后的第 $k$ 小元素。

本题考查有序性、二分搜索，以及第 k 小元素的前缀划分条件。

记两个有序表为 $A[1\ldots m]$、$B[1\ldots n]$，其中 $1\le k\le m+n$，相同取值按出现次数计入排名。假设可按下标在 $O(1)$ 时间访问元素。若某个表为空，直接返回另一个表的第 $k$ 项。

考虑从 $A$ 的前缀选出 $i$ 个元素，从 $B$ 的前缀选出 $j=k-i$ 个元素，使它们恰好构成合并后的前 $k$ 项。可行的 $i$ 必须满足

$$L=\max(0,k-n)\le i\le U=\min(k,m).$$

为统一边界，定义

$$A[0]=B[0]=-\infty,\qquad A[m+1]=B[n+1]=+\infty.$$

在 $[L,U]$ 上二分搜索。每轮取 $i=\lfloor(L+U)/2\rfloor$，令 $j=k-i$：

若

$$A[i]\le B[j+1],\qquad B[j]\le A[i+1],$$

则左侧的 $k$ 个元素均不大于右侧元素，返回 $\max\{A[i],B[j]\}$。

若 $A[i]>B[j+1]$，说明从 $A$ 中选多了，令 $U\leftarrow i-1$。任何 $i'\ge i$ 都有

$$A[i']\ge A[i]>B[k-i+1]\ge B[k-i'+1],$$

所以不可能是正确划分。若 $B[j]>A[i+1]$，则从 $A$ 中选少了，令 $L\leftarrow i+1$；任何 $i'\le i$ 同样都不满足划分条件。

下面的伪代码通过条件读取实现哨兵，不实际扩展输入表；数组下标从 $1$ 开始。

// 输入两张可随机访问的有序表，返回第 k 小元素；1 ≤ k ≤ m + n。
function KTH-TWO-SORTED(A, B, k):
    m ← length(A)
    n ← length(B)
    if m = 0:
        return B[k]
    if n = 0:
        return A[k]
    L ← max(0, k - n)
    U ← min(k, m)
    while L ≤ U:
        i ← floor((L + U) / 2)
        j ← k - i
        aLeft ← A[i] if i > 0 else -∞
        aRight ← A[i + 1] if i < m else +∞
        bLeft ← B[j] if j > 0 else -∞
        bRight ← B[j + 1] if j < n else +∞
        if aLeft ≤ bRight and bLeft ≤ aRight:
            return max(aLeft, bLeft)
        if aLeft > bRight:
            U ← i - 1
        else:
            L ← i + 1

概念上把两表归并后取前 $k$ 项，总能得到一个满足条件的前缀划分；每轮只排除不可能的划分，因此二分搜索必能找到答案。初始候选数至多为 $\min(m,n)+1$，故时间为

$$O\!\left(\log(\min\{m,n\}+1)\right),$$

满足要求的 $O(\log m+\log n)$ 上界，额外空间为 $O(1)$。

矩阵乘法

两个 $n\times n$ 矩阵 $X,Y$ 的乘积 $Z=XY$ 满足

$$Z_{ij}=\sum_{k=1}^{n}X_{ik}Y_{kj}.$$

共有 $n^2$ 个元素，每个元素需要 $O(n)$ 次标量运算，所以普通算法耗时 $O(n^3)$。一般情况下矩阵乘法不满足交换律，即 $XY\ne YX$；后面的分块公式必须保持因子的先后顺序。

把矩阵各分成四个 $n/2\times n/2$ 的块：

$$X=\begin{pmatrix}A&B\\C&D\end{pmatrix}, \qquad Y=\begin{pmatrix}E&F\\G&H\end{pmatrix}.$$

普通分块乘法为

$$XY= \begin{pmatrix} AE+BG & AF+BH\\ CE+DG & CF+DH \end{pmatrix}.$$

四个结果块各需两次半规模矩阵乘法，共八次；块加法总共 $O(n^2)$，所以 $T(n)=8T(n/2)+O(n^2)=O(n^3)$。

Strassen 算法把八次块乘法减少为七次。课件中的七个中间矩阵是

$$\begin{aligned} P_1&=A(F-H), & P_2&=(A+B)H,\\ P_3&=(C+D)E, & P_4&=D(G-E),\\ P_5&=(A+D)(E+H), & P_6&=(B-D)(G+H),\\ P_7&=(A-C)(E+F). \end{aligned}$$

用这些乘积恢复结果：

$$XY= \begin{pmatrix} P_5+P_4-P_2+P_6 & P_1+P_2\\ P_3+P_4 & P_1+P_5-P_3-P_7 \end{pmatrix}.$$

例如右上块 $P_1+P_2=A(F-H)+(A+B)H=AF+BH$；左下块 $P_3+P_4=(C+D)E+D(G-E)=CE+DG$。把其余两个块同样展开，可分别消去交叉项，得到 $AE+BG$ 和 $CF+DH$，因而与普通矩阵乘法完全相同。

取 $X=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$Y=\begin{pmatrix}5&6\\7&8\end{pmatrix}$。七个中间值依次是 $-2,24,35,8,65,-30,-22$；代入上式得到

$$XY=\begin{pmatrix}19&22\\43&50\end{pmatrix},$$

与普通矩阵乘法逐项计算的结果相同。

加减矩阵块共用 $O(n^2)$ 次标量运算，递推式为

$$T(n)=7T(n/2)+O(n^2) =O\!\left(n^{\log_27}\right) \approx O(n^{2.807}).$$

矩阵维度不是 2 的幂时可补零到最近的 2 的幂，维度增加不到一倍。这里的 $O(n^3)$ 与 $O(n^{\log_27})$ 都以标量加法和乘法次数计；若矩阵元素是会持续增长的大整数，还需另行分析每次标量运算的位复杂度。

分治练习

这一讲先复习分治的三个步骤，以及上一讲的主定理：拆成更小的同类子问题、递归求解、合并答案。下面两道练习分别对应确定性分治和随机分治。

练习：用 L 形骨牌覆盖一块 $n\times n$ 棋盘，其中 $n$ 是 2 的幂，且恰有一格不覆盖。

把棋盘分成四块 $n/2\times n/2$ 子棋盘。原来缺失的格子位于其中一块；在棋盘中心放置一块 L 形骨牌，恰好盖住其余三块各自靠中心的一格。于是每块子棋盘都恰好缺一格，可分别递归覆盖。$n=2$ 时，一块骨牌即可盖住剩余三格。

归纳可证整个构造不会重叠，也不会遗漏应覆盖的格子。骨牌数 $Q(n)$ 满足 $Q(2)=1$、$Q(n)=4Q(n/2)+1$，因此

$$Q(n)=\frac{n^2-1}{3}.$$

当 $n=4$ 时需 $(16-1)/3=5$ 块，与课件示例一致。若每次只需常数时间确定中心位置，构造整块棋盘的工作量是 $\Theta(n^2)$。

练习：分析 Karger-Stein 随机最小割算法的递归复杂度。

课件给出的过程是：小于 6 个顶点时直接枚举；否则独立运行两次随机收缩，每次将 $n$ 个顶点缩至约 $n/\sqrt2$ 个顶点，再对两个结果递归，并比较所得割。若每个递归结点的收缩和比较均可在 $O(n^2)$ 时间完成，则

$$T(n)=2T\!\left(\left\lceil\frac n{\sqrt2}\right\rceil\right)+O(n^2).$$

在主定理中 $a=2$、$b=\sqrt2$，而 $\log_{\sqrt2}2=2$，与本层指数 $d=2$ 相等。故时间上界为 $O(n^2\log n)$；若每层确实需要 $\Theta(n^2)$ 工作，则为 $\Theta(n^2\log n)$。这里分析的是运行时间，随机收缩的成功概率需要另行分析。

逆序对

逆序对是序列中满足 $i<j$ 且 $a_i>a_j$ 的一对位置。课件以歌曲偏好为例：若一人的排名顺序为 $1,2,\ldots,n$，另一人的排名按同样的歌曲顺序写成 $a_1,a_2,\ldots,a_n$，逆序对越少，两人的相对偏好越接近。例如 $[1,3,4,2,5]$ 只有 $(3,2)$ 和 $(4,2)$ 两个逆序对。

直接枚举所有 $i<j$ 需要 $\Theta(n^2)$ 时间。分治法把序列分成前半段 $A$ 和后半段 $B$：逆序对或完全落在 $A$，或完全落在 $B$，或由 $A$ 中一个元素和 $B$ 中一个元素组成。递归返回各半段的逆序对数及其排序结果；合并时同时统计跨半段的逆序对。

课件中的序列

$$[1,5,4,8,10\mid2,6,9,3,7]$$

左半段有 $1$ 对，右半段有 $3$ 对。按左半段的 $1,5,4,8,10$ 逐个数右半段中比它小的元素，分别得到 $0,2,2,4,5$ 对，跨半段合计 $13$ 对；总数为 $1+3+13=17$。

合并问题：若 $A$ 和 $B$ 已排序，如何数出所有 $a\in A,b\in B$ 且 $a>b$ 的配对？一种初步方法是对每个 $b\in B$ 在 $A$ 中二分查找，计算 $A$ 中比它大的元素数。课件示例中，排序后的 $A=[3,7,10,14,18]$、$B=[2,11,16,20,23]$；五个 $b$ 分别贡献 $5,2,1,0,0$ 对，共 $8$ 对。这样合并需 $O(n\log n)$ 时间，整棵递归树会达到 $O(n\log^2 n)$。

还可以利用归并排序的线性合并过程。设 $i,j$ 分别指向 $A,B$ 中尚未处理的首元素：

• 若 $A[i]\le B[j]$，就把 $A[i]$ 放入结果；它与当前及后续 $B$ 元素均不构成逆序对。
• 若 $A[i]>B[j]$，就把 $B[j]$ 放入结果；由于 $A$ 已排序，从 $A[i]$ 到末尾的 $|A|-i+1$ 个元素全都大于 $B[j]$，计数一次增加这么多。

余下的一侧直接接到结果末尾。整个过程的指针只向右移动，因此合并、计数均为 $O(|A|+|B|)$。相等元素应走第一分支，因为逆序对要求严格大于。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：MERGE-AND-COUNT}(A,B) \\[4pt] \hline \textbf{输入：}\ \text{两个已排序数组 }A,B \\ i=1,\ j=1,\ r=0,\ C=[\ ] \\ \textbf{while}\ i\le|A|\ \text{且}\ j\le|B|\ \textbf{do} \\ \qquad\textbf{if}\ A[i]\le B[j]\ \textbf{then}\ \text{将 }A[i]\text{ 接到 }C,\ i=i+1 \\ \qquad\textbf{else}\ r=r+|A|-i+1,\ \text{将 }B[j]\text{ 接到 }C,\ j=j+1 \\ \text{将 }A,B\text{ 尚未处理的元素依次接到 }C \\ \text{return}\ (r,C) \\ \hline \end{array}&& \end{aligned}$$

把合并计数嵌入归并排序，即得到 SORT-AND-COUNT：

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：SORT-AND-COUNT}(L) \\[4pt] \hline \textbf{输入：}\ \text{序列 }L \\ \textbf{if}\ |L|\le1\ \textbf{then}\ \text{return}\ (0,L) \\ \text{把 }L\text{ 分成前半段 }A\text{ 和后半段 }B \\ (r_A,A')=\text{SORT-AND-COUNT}(A) \\ (r_B,B')=\text{SORT-AND-COUNT}(B) \\ (r_{AB},C)=\text{MERGE-AND-COUNT}(A',B') \\ \text{return}\ (r_A+r_B+r_{AB},C) \\ \hline \end{array}&& \end{aligned}$$

正确性可对序列长度归纳：递归结果已分别正确统计两半内部的逆序对，并给出有序的 $A',B'$；MERGE-AND-COUNT 只统计跨半段的逆序对，且每一对恰被统计一次。因此返回的总数无重无漏，$C$ 也有序。递推式为

$$T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n) =\Theta(n\log n).$$

这个界按常数时间比较、索引和计数的通常模型计算；总数最多为 $n(n-1)/2$，需要 $O(\log n)$ 位来存储。

复数与单位根

快速傅里叶变换会在一组特殊的复数点上求多项式值。复数 $z=a+bi$ 可看成复平面上的点 $(a,b)$，也可写成极坐标形式

$$z=r(\cos\theta+i\sin\theta)=re^{i\theta}, \qquad r=\sqrt{a^2+b^2},$$

其中角度 $\theta$ 按 $2\pi$ 取模。例如 $-1=e^{i\pi}$、$i=e^{i\pi/2}$、$5+5i=5\sqrt2e^{i\pi/4}$。极坐标下相乘时，模长相乘、角度相加：

$$(r_1e^{i\theta_1})(r_2e^{i\theta_2}) =r_1r_2e^{i(\theta_1+\theta_2)}.$$

因此 $-z=re^{i(\theta+\pi)}$。若 $|z|=1$，则 $z^n=e^{in\theta}$；这就把求 $z^n=1$ 转化为求角度。

$n$ 次单位根：令 $\omega=e^{2\pi i/n}$，则方程 $z^n=1$ 的 $n$ 个互异解为 $1,\omega,\omega^2,\ldots,\omega^{n-1}$。

当 $n$ 为偶数时，$\omega^{j+n/2}=-\omega^j$，单位根可两两配成相反数；同时 $\omega^{2j}=(\omega^2)^j$，而 $\omega^2$ 是原始的 $n/2$ 次单位根。也就是说，将配对的点平方后，得到规模减半但结构相同的一组点。这正是后文递归可以继续进行的原因。

图中以 $n=16$ 展示单位圆上的 16 个根：相隔 $\pi$ 的点互为相反数；它们平方后角度加倍，方框标出的 8 个点恰是 8 次单位根。图片已通过 PicList 上传至图床。

复共轭将在插值时使用。若 $z=re^{i\theta}=a+bi$，则 $\overline z=re^{-i\theta}=a-bi$。向量的内积取共轭：

$$\langle u,v\rangle=\sum_{j=0}^{n-1}u_j\overline{v_j}.$$

内积为零时，两个复向量正交。对矩阵逐项取共轭再转置，得到共轭转置 $M^*$；要注意它与仅逐项取共轭不同。

多项式乘法

设两个次数至多为 $d$ 的多项式为

$$A(x)=\sum_{j=0}^{d}a_jx^j, \qquad B(x)=\sum_{j=0}^{d}b_jx^j.$$

乘积 $C(x)=A(x)B(x)=\sum_{k=0}^{2d}c_kx^k$ 的系数满足卷积公式

$$c_k=\sum_{j=0}^{k}a_jb_{k-j},$$

其中越过 $0,\ldots,d$ 的系数视为零。逐个按此式计算全部 $2d+1$ 个系数需要 $\Theta(d^2)$ 次基本算术运算。

多项式还有取值表示：次数不超过 $d$ 的多项式在任意 $d+1$ 个互异点上的值，能够唯一确定其系数。证明很简单：若两个这样的多项式在这些点上相等，它们的差次数至多为 $d$，却有 $d+1$ 个不同的根，只能是零多项式。系数转取值称为求值；取值转系数称为插值。

乘积次数至多为 $2d$，因此选取 $n\ge2d+1$ 个互异点 $x_0,\ldots,x_{n-1}$ 即可：

1. 在这些点上分别计算 $A(x_j)$ 和 $B(x_j)$；
2. 逐点相乘，得到 $C(x_j)=A(x_j)B(x_j)$；
3. 从 $C$ 的这些值插值恢复全部系数。

已知两组取值时，第二步只需 $O(n)$ 次乘法。难点是第一步和第三步：直接在每个点上求值要 $O(n)$ 时间，全部点就要 $\Theta(n^2)$；直接插值也没有带来速度优势。快速傅里叶变换（FFT）为特殊的取值点同时实现 $O(n\log n)$ 的求值和插值。此处沿用课件的单位成本模型，假设实数或复数的基本算术运算可视为常数时间。

快速求值

把 $A(x)$ 的偶数次项和奇数次项分开。以课件中的多项式为例，

$$3+4x+6x^2+2x^3+x^4+10x^5 =(3+6x^2+x^4)+x(4+2x^2+10x^4).$$

一般地，设

$$A_e(t)=a_0+a_2t+a_4t^2+\cdots, \qquad A_o(t)=a_1+a_3t+a_5t^2+\cdots,$$

则 $A(x)=A_e(x^2)+xA_o(x^2)$。因此对一对相反的点 $x,-x$，只须各求一次 $A_e(x^2)$ 和 $A_o(x^2)$，再用常数次运算得到

$$A(x)=A_e(x^2)+xA_o(x^2), \qquad A(-x)=A_e(x^2)-xA_o(x^2).$$

课件提问：怎样选点，才能在下一层继续递归？

下一层的点是本层一半点的平方，因此它们也必须可以两两配成相反数。从最底层的点 $1$ 反向看，上层是 $\pm1$，再上层需要 $\pm1,\pm i$。平方可能为负数，故必须使用复数。继续上推，得到 $n$ 次复单位根；它们平方后正好成为 $n/2$ 次单位根。

取 $n$ 为 2 的幂、$\omega=e^{2\pi i/n}$，将不足 $n$ 项的系数在末尾补零。FFT 计算的就是

$$\operatorname{FFT}(a,\omega) =\bigl(A(1),A(\omega),\ldots,A(\omega^{n-1})\bigr), \qquad a=(a_0,\ldots,a_{n-1}).$$

递归对偶数下标系数和奇数下标系数分别调用 FFT，使用 $\omega^2$ 作为 $n/2$ 次单位根，再合并两组结果：

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：FFT}(a,\omega) \\[4pt] \hline \textbf{输入：}\ a=(a_0,\ldots,a_{n-1}),\ n\text{ 是 2 的幂；}\omega\text{ 是原始 }n\text{ 次单位根} \\ \textbf{if}\ n=1\ \textbf{then}\ \text{return}\ (a_0) \\ s=\text{FFT}((a_0,a_2,\ldots,a_{n-2}),\omega^2) \\ t=\text{FFT}((a_1,a_3,\ldots,a_{n-1}),\omega^2) \\ \textbf{for}\ j=0\ \textbf{to}\ n/2-1\ \textbf{do} \\ \qquad r_j=s_j+\omega^jt_j \\ \qquad r_{j+n/2}=s_j-\omega^jt_j \\ \text{return}\ (r_0,r_1,\ldots,r_{n-1}) \\ \hline \end{array}&& \end{aligned}$$

这里 $s_j=A_e(\omega^{2j})$、$t_j=A_o(\omega^{2j})$。第一个合并式正是 $A(\omega^j)$；第二个利用 $\omega^{j+n/2}=-\omega^j$，得到 $A(\omega^{j+n/2})$。于是递归算法正确。每层只需 $O(n)$ 次复数运算，递推为

$$T(n)=2T(n/2)+O(n)=O(n\log n).$$

课件的第一版伪代码按 $j=0,\ldots,n-1$ 分别计算所有取值；上面把相反数成对写出，明确了复用关系与每层的线性代价。

快速插值

设 $a=(a_0,\ldots,a_{n-1})^{\mathsf T}$，在 $n$ 次单位根上求值所得的向量为 $y$。用 $j,k=0,\ldots,n-1$ 作行、列下标，定义傅里叶矩阵

$$M_n(\omega)_{jk}=\omega^{jk}.$$

于是 $y=M_n(\omega)a$。对任意互异的取值点，类似的矩阵是 Vandermonde 矩阵，点互异就可逆；一般方法即使能在 $O(n^2)$ 时间内求出插值，也达不到 FFT 所需的 $O(n\log n)$。单位根使这个矩阵具备更强的结构。

引理：傅里叶矩阵的不同列相互正交，且每列的内积平方长度为 $n$。

证明：第 $j$ 列与第 $k$ 列的共轭内积为

$$\sum_{r=0}^{n-1}\omega^{r(j-k)}.$$

若 $j=k$，每项都是 1，和为 $n$；若 $j\ne k$，该式是公比 $\omega^{j-k}\ne1$ 的几何级数，且 $\omega^{n(j-k)}=1$，所以

$$\sum_{r=0}^{n-1}\omega^{r(j-k)} =\frac{1-\omega^{n(j-k)}}{1-\omega^{j-k}}=0.$$

由此 $M_n(\omega)^*M_n(\omega)=nI$。由于傅里叶矩阵是方阵，$M_n(\omega)^{-1}=\frac1nM_n(\omega)^*$；而它关于主对角线对称，$M_n(\omega)^*=M_n(\omega^{-1})$，故

$$\boxed{M_n(\omega)^{-1}=\frac1nM_n(\omega^{-1})}.$$

这说明插值只需再运行一次 FFT，并将结果逐项除以 $n$：

$$\boxed{a=\frac1n\operatorname{FFT}(y,\omega^{-1})}.$$

同样的偶、奇下标拆分适用于逆单位根 $\omega^{-1}$，因此插值也是 $O(n\log n)$。课件把它描述为从傅里叶基到系数基的逆变换；准确地说，矩阵除以 $\sqrt n$ 后是酉矩阵，逆变换由其共轭转置给出。

FFT 乘法

至此可以把多项式乘法的四个步骤具体化。对次数至多为 $d$ 的 $A,B$，取不小于 $2d+1$ 的最小 2 的幂 $n$，把两组系数补零至长度 $n$，令 $\omega=e^{2\pi i/n}$：

$$\begin{aligned} u&=\operatorname{FFT}(a,\omega),\\ v&=\operatorname{FFT}(b,\omega),\\ w_j&=u_jv_j\quad(0\le j<n),\\ c&=\frac1n\operatorname{FFT}(w,\omega^{-1}). \end{aligned}$$

最后取 $c_0,\ldots,c_{2d}$ 即为乘积系数。选 $n\ge2d+1$ 至关重要：它保证乘积次数小于 $n$，不会在循环下标的取值过程中把高次系数折回低次系数。

例如 $A(x)=1+x$、$B(x)=1-x$，取 $n=4$、$\omega=i$。在 $1,i,-1,-i$ 四点上，两组取值分别是 $(2,1+i,0,1-i)$ 与 $(0,1-i,2,1+i)$；逐点相乘为 $(0,2,0,2)$。逆 FFT 后得到系数 $(1,0,-1,0)$，即 $C(x)=1-x^2$。

两次正向 FFT、一次逆向 FFT 各耗时 $O(n\log n)$，逐点相乘耗时 $O(n)$。由于最小的 2 的幂满足 $n<2(2d+1)$，总时间为 $O(d\log d)$（$d\ge1$），相较直接卷积的 $\Theta(d^2)$ 有渐近改进。这里分析的是复数算术操作数；若使用有限精度浮点数，还需关注舍入误差。