递归与分治策略：算法设计、正确性证明与复杂度分析

2026年11月5日笔记算法 zh-CN

分治法（Divide-and-Conquer）是算法设计中最基本且强大的范式之一。其核心思想是将一个难以直接解决的大规模问题，递归地划分为若干个规模较小、相互独立且与原问题结构完全相同的子问题，分别求解后再将各子问题的局部解合并为原问题的全局解。

一、分治策略架构与理论前提

一个标准的分治算法严格由三个阶段构成：

分解（Divide）：将原问题划分为若干个规模较小、相互独立且与原问题结构同构的子问题；
解决（Conquer）：若子问题规模足够小（达到递归基 Base Case），则直接求解并返回；否则递归调用分治过程；
合并（Combine）：将各子问题的解组装为原问题的全局解。

flowchart TD
    Problem["原问题规模 n"] --> Sub1["独立子问题 1 (规模 n/b)"]
    Problem --> Sub2["独立子问题 2 (规模 n/b)"]
    Problem --> SubA["独立子问题 a (规模 n/b)"]
    Sub1 --> Solve1["递归求解 / 递归基"]
    Sub2 --> Solve2["递归求解 / 递归基"]
    SubA --> SolveA["递归求解 / 递归基"]
    Solve1 --> Combine["合并阶段 Combine: 代价 f(n)"]
    Solve2 --> Combine
    SolveA --> Combine
    Combine --> Solution["原问题全局解"]

1.1 分治法适用的四大先决条件

规模缩减可解性：原问题随着规模的缩小而更容易求解；
最优子结构与子问题同构性：原问题可以分解为若干个规模较小的同类子问题；
子解可合并性：利用各子问题的解能够以较低的计算开销（通常为多项式或线性时间 $f(n)$ ）合并为原问题的解；
子问题相互独立性：各个子问题之间不包含公共的子子问题。
- 说明：若子问题之间存在大量重叠计算，使用分治法将导致相同子问题的指数级重复求解，此时应转向动态规划。

二、二分查找与循环不变量规范

二分查找是减治策略（Decrease-and-Conquer）的典型代表，每次通过常数次比较将搜索区间规模缩小一半。

2.1 左闭右开区间 $[left, right)$ 的设计与代码实现

以在升序序列中查找首个不小于目标值的位置（lower_bound）为例：

int lowerBound(const std::vector<int>& a, int target) {
    int left = 0;
    int right = static_cast<int>(a.size()); // 搜索区间为左闭右开 [left, right)
    
    while (left < right) {
        int mid = left + (right - left) / 2; // 防止整数加法溢出
        if (a[mid] < target) {
            left = mid + 1; // [mid+1, right)
        } else {
            right = mid;    // [left, mid)
        }
    }
    return left; // 终止时 left == right
}

2.2 循环不变量的形式化证明

循环不变量是在循环的整个生命周期中保持恒真的逻辑断言，证明遵循类似数学归纳法的三个步骤：

定义不变量：
1. 对于所有 $k \in [0, left - 1]$ ，恒有 $a[k] < target$ ；
2. 对于所有 $k \in [right, n - 1]$ ，恒有 $a[k] \ge target$ 。
初始化（Initialization）：
在首轮循环开始前， $left = 0, right = n$ 。区间 $[0, -1]$ 与 $[n, n-1]$ 均为空集，不变量显然真空成立。
保持（Maintenance）：
在某轮循环开始前，设不变量成立。计算 $mid = \lfloor (left + right)/2 \rfloor$ $mi d = ⌊(l e f t + r i g h t) /2 ⌋$ ：
- 若 $a[mid] < target$ ：由数组升序排列，对任意 $k \le mid$ ，恒有 $a[k] \le a[mid] < target$ 。更新 $left = mid + 1$ 后，新区间 $[0, left-1]$ 中的所有元素依然严格小于 $target$ ，不变量得到保持；
- 若 $a[mid] \ge target$ ：由升序排列，对任意 $k \ge mid$ ，恒有 $a[k] \ge a[mid] \ge target$ 。更新 $right = mid$ 后，新区间 $[right, n-1]$ 中的所有元素依然大于或等于 $target$ ，不变量得到保持。
终止（Termination）：
当 $left = right$ 时循环终止。根据不变量， $a[0 \dots left-1] < target$ 且 $a[left \dots n-1] \ge target$ 。因此，返回值 $left$ 恰好为首个不小于 $target$ 的元素下标（若 $left = n$ ，表示全数组元素均小于目标）。

三、归并排序与逆序对统计

归并排序（Merge Sort）将待排序列二等分，递归排序后利用双指针在线性时间内合并两个有序子序列。其递推关系为：

T(n) = 2T(n/2) + \Theta(n) \implies T(n) = \Theta(n\log n).

标准实现需要开辟一个大小为 $n$ 的辅助数组以暂存合并结果，因此空间复杂度为主导的 $\Theta(n)$ 。双指针在元素相等时优先取左侧子数组元素，从而严格保证排序的稳定性（Stability）。

3.1 利用归并排序统计逆序对（Inversion Pairs）

问题背景：给定数组 $a[0 \dots n-1]$ ，若下标 $i < j$ 且数值 $a[i] > a[j]$ ，则称 $(a[i], a[j])$ 为一个逆序对。暴力枚举所有二元组需要 $O(n^2)$ 时间。

分治推导：
将数组划分为左半部分 $L[0 \dots m-1]$ 与右半部分 $R[0 \dots k-1]$ 。整个数组的逆序对总数等于：
$\text{总逆序对数} = \text{左半段内部逆序对} + \text{右半段内部逆序对} + \text{跨越左右两半的逆序对}.$

在前两项递归求解完毕后， $L$ 与 $R$ 均已局部有序。在执行双指针合并时：

设当前比对元素为 $L[i]$ 与 $R[j]$ ；
若 $L[i] \le R[j]$ ：正常推进左指针，不产生跨越逆序对；
若 $L[i] > R[j]$ ：由于子数组 $L$ 已升序排列，从当前位置 $i$ 开始到末尾 $m-1$ 的所有剩余元素均严格大于 $R[j]$ 。
因此，当前右侧元素 $R[j]$ 与左半段剩余的所有元素 $(L[i], L[i+1], \ldots, L[m-1])$ 均构成逆序对。
计数动作：无需遍历，直接一次性累加跨越逆序对数：
$\Delta \leftarrow (m - i).$

long long mergeAndCount(std::vector<int>& a, int l, int mid, int r, std::vector<int>& temp) {
    int i = l, j = mid + 1, k = l;
    long long inv_count = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            inv_count += (mid - i + 1); // 批量累加跨越逆序对
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r)   temp[k++] = a[j++];
    for (i = l; i <= r; ++i) a[i] = temp[i];
    return inv_count;
}

该算法在完成排序的同时精确统计出逆序对总数，时间复杂度为严密的 $\Theta(n\log n)$ 。

四、快速排序与第 $k$ 小元素选择算法（Quick Select）

4.1 快速排序的划分思想

快速排序选取基准元素（Pivot），通过一次划分（Partition）将数组调整为两部分：左侧元素均不大于 Pivot，右侧元素均不小于 Pivot，Pivot 最终就位至确定的全局位置 $p$ 。

T(n) = T(p) + T(n - p - 1) + \Theta(n).

平均性能：随机选取 Pivot 时，期望划分较为均匀，递推为 $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$ ；
最坏性能：若划分极度不平衡（例如每次单侧为空）， $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$ ；
三路划分优化（Three-way Partitioning）：对于含有海量重复元素的数据集，将序列划分为 $< \text{Pivot}$ 、 $= \text{Pivot}$ 、 $> \text{Pivot}$ 三段，可防止二次方退化。

4.2 快速选择算法（Quick Select）与线性期望时间

问题定义：在无序数组中寻找第 $k$ 小的元素。若通过全排序求解，耗时为 $\Theta(n\log n)$ 。

单侧递归机制：
执行一次划分后，设 Pivot 归位后的绝对下标为 $p$ ：

若 $p = k$ ，当前元素即为目标，直接返回；
若 $k < p$ ，目标元素必定落在左半段，仅递归左子数组；
若 $k > p$ ，目标元素必定落在右半段，仅递归右子数组。

复杂度数学推导：
与快速排序不同，Quick Select 仅向单个分支递归。在平均平衡划分假定下，各阶段子问题规模依序为 $n, n/2, n/4, \dots$ ：

E[T(n)] = \sum_{i=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^i} = n \sum_{i=0}^{\lfloor \log_2 n \rfloor} \left(\frac{1}{2}\right)^i < 2n = \Theta(n).

因此，快速选择算法的数学期望时间复杂度为线性阶 $\Theta(n)$ 。

最坏情况的确定性保证：采用 BFPTR 算法（五元中位数取中位数算法），通过将数据分为 5 元素一组并寻找中位数的中位数作为 Pivot，可严格保证每次划分至少淘汰 $3n/10$ 个元素，导出递推式：
$T(n) \le T(\lceil n/5 \rceil) + T(7n/10 + 6) + O(n) = O(n).$
从而在最坏情况下也能提供严密的确定性线性时间上界。

五、降低递归分支数的高效分治

标准分治算法中，若子问题数量过多，往往导致复杂度急剧上升。通过代数变换减少子问题个数，可显著提升渐近性能。

5.1 Karatsuba 大整数乘法算法

计算两个 $n$ 位大整数 $X, Y$ 的乘积。将两数均按高低 $m = n/2$ 位分解：
$X = a \cdot 2^m + b,\qquad Y = c \cdot 2^m + d.$

常规代数展开式为：
$X \cdot Y = ac \cdot 2^{2m} + (ad + bc) \cdot 2^m + bd.$
直接递归计算需要 4 次小规模乘法（ $ac, ad, bc, bd$ ），递推式为 $T(n) = 4T(n/2) + O(n)$ ，由主定理得 $T(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$ ，无性能提升。

Karatsuba 的代数优化：
交叉项可表示为：
$ad + bc = (a + b)(c + d) - ac - bd.$
由于项 $ac$ 与 $bd$ 必须独立计算，因此只需额外递归计算一次乘法 $(a+b)(c+d)$ ，随后通过两次减法即可得到交叉项。总递归乘法次数从 4 次减少至 3 次：

T(n) = 3T(n/2) + O(n) \implies T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585}).

5.2 Strassen 矩阵乘法算法

计算两个 $n \times n$ 矩阵的乘积，经典矩阵乘法需执行 $n^3$ 次标量乘法。标准分块矩阵乘法需计算 8 个子矩阵乘积：
$T(n) = 8T(n/2) + O(n^2) \implies T(n) = \Theta(n^3).$

Strassen 通过构造 7 个精妙的辅助矩阵 $M_1, \ldots, M_7$ （每个 $M_i$ 仅含一次子矩阵递归乘法），随后在线性加减法内组合出结果子块：

T(n) = 7T(n/2) + \Theta(n^2) \implies T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}).

方法论本质：在现代计算架构中，加减法代价远低于高精度乘法。利用常数次加减运算置换昂贵的递归乘法分支，可实现渐近复杂度的指数级下降。

六、几何与构造性分治经典问题

6.1 残缺棋盘覆盖问题（Tromino Tiling）

问题：在一个 $2^k \times 2^k$ 个方格构成的棋盘上，恰有一个特殊方格缺失。要求使用 L 型三格骨牌（覆盖 3 个方格）铺满所有正常方格，骨牌不得重叠。

分治构造机理：

将棋盘均匀划分为四个 $2^{k-1} \times 2^{k-1}$ 的子象限；
原始特殊缺格必然且仅能落入其中一个子象限；
关键构造（人造缺格）：在棋盘中心处放置一块 L 型骨牌，使其三个小方块分别占据其余三个原本完好无损的子象限的中心邻接角格；
此时，所有四个子象限均恰好包含一个“缺格”（一个为天然缺格，其余三个为人工构造缺格）；
四个子问题结构完全同构，直接递归求解。

T(n) = 4T(n/2) + O(1) \implies T(n) = \Theta(n^2) = \Theta(N).

所需 L 型骨牌总数严格满足 $(4^k - 1) / 3$ 块。

6.2 二维平面最接近点对问题（Closest Pair）

问题：给定平面上 $n$ 个点的集合，寻找欧氏距离最近的点对。暴力比对耗时 $\Theta(n^2)$ 。

分治推导与条带约束：

将点集按横坐标排序，以垂直分割线 $x = m$ 将点集等分为左右两半 $P_L, P_R$ ；
递归求得左右两侧内部的最近点距分别为 $\delta_L, \delta_R$ ，记 $\delta = \min(\delta_L, \delta_R)$ ；
合并阶段考察：跨越分割线的最近点对，其横坐标必然落在垂直条带区域 $[m - \delta, m + \delta]$ 内；
几何稀疏性证明（鸽巢原理）：
- 将条带内的点按纵坐标 $y$ 升序排列；
- 考察一个高为 $\delta$ 、宽为 $2\delta$ 的矩形区域。由于左半部分和右半部分内部任意两点的距离均不小于 $\delta$ ，在几何上，左侧边长为 $\delta \times \delta$ 的半矩形内最多只能容纳 4 个点，右侧同理；
- 因此，条带内的任意一点，在纵坐标排序序列中向后比对至多 6 到 7 个邻近点，即可覆盖所有距离小于 $\delta$ 的候选点。

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

七、分治算法答题规范与常见易错辨析

算法 / 典型题	答题书写规范关键点	常见失分陷阱
二分查找	严格声明搜索区间的开闭状态（如 $[left, right)$ ），给出循环终止条件及指针移动步进	混淆 `right = mid` 与 `right = mid - 1` 导致越界或死循环
归并与逆序对	明确双指针合并过程、临时辅助数组开辟及批量累加跨越项公式	误将辅助空间写为 $O(\log n)$ （遗漏临时数据存储数组 $O(n)$ ）
快速选择	明确划分后的单侧递归判定条件，说明期望线性时间证明依据	混淆平均期望复杂度 $O(n)$ 与最坏情况复杂度 $O(n^2)$
棋盘覆盖	明确四象限划分逻辑及中心 L 型骨牌制造人工缺格的构造原则	误将中心骨牌放置在已包含天然缺格的象限中
平面最近点对	阐明 $2\delta$ 垂直条带约束及按 $y$ 坐标排序后只需检查常数点的几何依据	合并阶段未按 $y$ 排序而直接双重循环，导致复杂度退化为 $O(n^2)$