算法：分治法

分治法可以将较大规模的问题分解成若干个与原问题相似的子问题，求解后合并到原问题，从而优化复杂度。

分治算法的要点：

确定问题模型
确定拆分（合并）性质
确定分治终点的解法

原理

步骤	作用	复杂度
Divide	整个问题划分为多个子问题	$D(n)$
Conquer	求解各个子问题	$\displaystyle a T \left( \frac{n}{b} \right)$
Combine	合并子问题的解，形成原问题的解	$C(n)$

据此可建立递归方程：

$$T(n) = aT\left( \frac{n}{b} \right) + D(n) + C(n)$$

二分法

二分法就是分治法的一种常见实现，核心是子问题的规模是原问题的 $\displaystyle \frac{1}{2}$

案例

归并排序

详细内容见此处：归并排序

归并排序

归并排序的递归方程：

$$T(n) = 2T \left(\frac{n}{2}\right) + \mathrm{O} (n) = \mathrm{O} (n \log n)$$

快速排序

详细内容见此处：快速排序

折半查找

详细内容见此处：折半查找

实际上，对于长度为 $n$ 的有序序列（例如[10, 20, 30, 40, 50, 60]），折半查找构建了深度为 $h = \log(n+1)$ 的判定树。

折半搜索的判定树

折半查找的平均搜索长度

$$\begin{align*} ASL &= \frac{1}{n} \left(1 \times 2^0 + 2 \times 2^1 + 3 \times 2^2 + \cdots + (h-1) \times 2^{h-2} + h \times 2^{k-1}\right) \\ &= \frac{(h-1) \times 2^k + 1}{n} \\ &= \mathrm{O}(\log(n+1)) \end{align*}$$

大整数乘法

$n$ 位二进制整数 $X$ 和 $Y$ 相乘，通常算法的时间复杂度为 $\mathrm{O} (n^2)$。

尝试将数字平均分成两部分：

大整数乘法

此时乘法转化为：

$$\begin{align*} XY &= (A \cdot 2^{\frac{n}{2}} + B) \cdot (C \cdot 2^{\frac{n}{2}} + D) \\ &= AC \cdot 2^n + (AD + BC) \cdot 2^{\frac{n}{2}} + BD \\ &= AC \cdot 2^{n} + ((A+B)(C+D)-AC-BD) \cdot 2^{\frac{n}{2}} + BD \end{align*}$$

根据

$$XY = AC \cdot 2^{n} + ((A+B)(C+D)-AC-BD) \cdot 2^{\frac{n}{2}} + BD$$

可得递归方程为

$$T(n) = 3T \left(\frac{n}{2}\right) + \Theta(n)$$

由主定理可知它的复杂度为 $\Theta(n^{1.59})$

📝 备注

中间式
$$XY = AC \cdot 2^n + (AD + BC) \cdot 2^{\frac{n}{2}} + BD$$
并不能降低复杂度，因为它的递归方程
$$T(n) = 4 \left(\frac{n}{2}\right) + \Theta(n)$$
复杂度为 $\Theta(n^2)$。

矩阵乘法

两个 $n \times n$ 的矩阵 $\bm{A}$ 和 $\bm{B}$ 相乘，普通计算方法的时间复杂度为 $\Theta(n^3)$

将 $\bm{A}$ 和 $\bm{B}$ 分成 $4$ 个大小为 $\displaystyle \frac{n}{2} \times \frac{n}{2}$ 的子矩阵，则有

$$\left[ \begin{matrix} \bm{C}_{11} & \bm{C}_{12} \\ \bm{C}_{21} & \bm{C}_{22} \end{matrix} \right] = \left[ \begin{matrix} \bm{A}_{11} & \bm{A}_{12} \\ \bm{A}_{21} & \bm{A}_{22} \end{matrix} \right] \times \left[ \begin{matrix} \bm{B}_{11} & \bm{B}_{12} \\ \bm{B}_{21} & \bm{B}_{22} \end{matrix} \right] $$

令

$$\left\{ \begin{array}{c} \begin{align*} \bm{M}_1 &= \bm{A}_{11} (\bm{B}_{12}-\bm{B}_{12}) \\ \bm{M}_2 &= (\bm{A}_{21} + \bm{A}_{12}) \bm{B}_{11} \\ \bm{M}_3 &= (\bm{A}_{21} + \bm{A}_{22}) \bm{B}_{11} \\ \bm{M}_4 &= \bm{A}_{22} (\bm{B}_{21} - \bm{B}_{11}) \\ \bm{M}_5 &= (\bm{A}_{11} + \bm{A}_{22}) (\bm{B}_{11} + \bm{B}_{22}) \\ \bm{M}_6 &= (\bm{A}_{12} - \bm{A}_{22}) (\bm{B}_{21} + \bm{B}_{22}) \\ \bm{M}_7 &= (\bm{A}_{11} - \bm{A}_{21}) (\bm{B}_{11} + \bm{B}_{12}) \end{align*} \end{array} \right.$$

则有

$$\left\{ \begin{array}{c} \begin{align*} \bm{C}_{11} &= \bm{M}_5 + \bm{M}_4 - \bm{M}_2 + \bm{M}_6 \\ \bm{C}_{12} &= \bm{M}_1 + \bm{M}_2 \\ \bm{C}_{21} &= \bm{M}_3 + \bm{M}_4 \\ \bm{C}_{22} &= \bm{M}_5 + \bm{M}_1 - \bm{M}_3 - \bm{M}_7 \end{align*} \end{array} \right.$$

此时它的递归方程为

$$T(n) = 7 \left(\frac{n}{2}\right) + \Theta(n^2)$$

复杂度为 $\Theta(n^{\log_{2} 7}) = \Theta(n^{2.81})$

降低矩阵乘法的复杂度一直是算法设计的重要问题。目前，已有算法可将其复杂度降低为 $\Theta(n^{2.376})$

第k小元素

第 $k$ 小元素表述为在有 $n$ 个元素的数组 $S$ 中，找到第 $k$ 小的元素。

若 $\mid S \mid \leqslant 50$，则采用堆排序

否则：

将 $n$ 个元素分为 $\displaystyle \left\lceil \frac{n}{5} \right\rceil$ 组，每组5个元素，每组排序。复杂度为 $\mathrm{O} (n)$
将每组第3个元素取出，得到大小为 $\displaystyle \left\lceil \frac{n}{5} \right\rceil$ 的数组 $M$。

若最后一组中的元素可能不足5个，则1个取出、2个取较小、3个取中间、4个取第二小。

从数组 $M$ 中找到第 $\displaystyle \left\lceil \frac{|M|}{2} \right\rceil$ 个元素 $m$，复杂度为 $\displaystyle T\left(\left\lceil \frac{n}{5} \right\rceil\right)$。

此时 $S$ 中至少有 $\displaystyle 3\left(\left\lceil \frac{1}{2} \left\lceil \frac{n}{5} \right\rceil \right\rceil -2 \right) \geqslant \frac{3n}{10} - 6$ 个元素大于等于 $m$；

至少有 $\displaystyle \frac{3n}{10}-6$ 个元素小于等于 $m$

依次扫描整个数组 $S$，并构建三个临时数组 $S_1, S_2, S_3$：当 $s_i < m$ 时放入 $S_1$，$s_i = m$ 时放入 $S_2$；$s_i > m$ 时放入 $S_3$。

$S_1$ 最多有 $\displaystyle n - \left(\frac{3n}{10} - 6\right) = \frac{7}{10} + 6$ 个元素。

$S_3$ 最多有 $\displaystyle n - \left(\frac{3n}{10} - 6\right) = \frac{7}{10} + 6$ 个元素。

当 $k \leqslant |S_1|$ 时，返回 $S_1$ 的第 $k$ 个元素；当 $|S_1| < k \leqslant |S_1| + |S_2|$ 时，返回 $m$；当 $k > |S_1| + |S_2|$ 时，返回 $S_3$ 的第 $k - |S_1| - |S_2|$ 个元素。

综上，时间复杂度

$$T(n) = T\left(\left\lceil \frac{n}{5} \right\rceil\right) + T\left(\frac{7n}{10} + 6\right) + \mathrm{O}(n) \leqslant \mathrm{O}(n)$$

证明

使用第二数学归纳法：当 $n < 50$ 时，使用堆排序，显然成立。

假设 $n \leqslant m$ 时，$T(m) = \mathrm{O}(m)$，$T(m) \leqslant cm$，则当 $n=m+1$ 时，有

$$\begin{align*} T(m+1) &= T\left(\left\lceil \frac{m+1}{5} \right\rceil\right) + T \left(\frac{7(m+1)}{10} + 6\right) + \mathrm{O}(m+1) \\ & \leqslant c_1 \left\lceil \frac{m+1}{5} \right\rceil + c_2 \left(\frac{7(m+1)}{10} + 6\right) + \mathrm{O}(m+1) \\ & \leqslant c \left(\frac{m+1}{5} + 1\right) + c\left(\frac{7(m+1)}{10} + 6\right) + a(m+1) \\ &= \left(\frac{9c}{10} + a\right)(m+1) + 7c \\ & \leqslant \mathrm{O}(m+1) \end{align*}$$

得证。

平衡

平衡与分治法密不可分，使用分治法和递归时要尽量把问题分成规模相等或至少是规模相近的子问题。

以排序为例：

冒泡排序：找出最小元素，再对剩下的 $n-1$ 个元素排序，划分规模为 $1$ 和 $n-1$。时间复杂度 $T(n)=T(n-1)+(n-1)$，则 $$T(n)=\sum_{i=1}^{n-1} i =\Theta(n^2)$$
归并排序：划分成一个规模为 $\displaystyle \left\lfloor \frac{n}{2} \right\rfloor$ ，另一个规模为 $\displaystyle \left\lceil \frac{n}{2} \right\rceil$ 的子表排序，再以 $\mathrm{O}(n)$ 时间归并。时间复杂度 $$T(n)=T\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+T\left(\left\lceil\frac{n}{2}\right\rceil\right)+O(n) = 2T\left(\frac{n}{2}\right)+O(n)=\Theta(n\log n)$$

显然归并排序好。在使用分治法和递归时，要尽量把问题分成规模相等或至少是规模相近的子问题，即做到平衡。