分治算法与经典问题 (Divide and Conquer)

分治算法（Divide and Conquer） 是计算机科学中最基本、也是最强大的算法范式之一。它的核心思想在于“分而治之”：将一个规模庞大的复杂问题分解为若干个规模较小但形式完全相同的子问题，递归求解后再将子问题的结果合并为原问题的解。

---

1. 分治三步法与主定理

1.1 分治三步架构

flowchart TD
    A["原问题规模 N"] --> B["1. 分解 (Divide)<br>切分为 a 个规模为 N/b 的子问题"]
    B --> C1["子问题 1 (递归求解)"]
    B --> C2["子问题 2 (递归求解)"]
    B --> Ck["子问题 a (递归求解)"]
    C1 --> D["3. 合并 (Combine)<br>耗费 f(N) 时间整合子问题解"]
    C2 --> D
    Ck --> D
    D --> E["原问题最终解"]

1. 分解（Divide）：将原问题切分为 \(a\) 个独立的子问题，每个子问题的规模为 \(n / b\)；
2. 解决（Conquer）：递归求解各个子问题。当子问题规模足够小（到达递归基底）时直接求解；
3. 合并（Combine）：将各子问题的解合并为原问题的解。

---

1.2 主定理 (Master Theorem) 复杂度速查

对于满足递推关系式 \(T(n) = a T(n / b) + f(n)\) 的分治算法（其中 \(a \ge 1, b > 1\)）：

令临界指数为 \(c_{crit} = \log_b a\)：

关系条件	时间复杂度 \(T(n)\)	典型算法实例
\(f(n) = \mathcal{O}(n^c)\) 且 \(c < \log_b a\)	\(\mathcal{O}(n^{\log_b a})\)	Karatsuba 大整数乘法 (\(a=3, b=2 \implies \mathcal{O}(n^{1.585})\))
\(f(n) = \Theta(n^c \log^k n)\) 且 \(c = \log_b a\)	\(\mathcal{O}(n^{\log_b a} \log^{k+1} n)\)	归并排序 (\(a=2, b=2, c=1, k=0 \implies \mathcal{O}(n \log n)\))
\(f(n) = \Omega(n^c)\) 且 \(c > \log_b a\)	\(\mathcal{O}(f(n))\)	快速选择平均复杂度 (\(a=1, b=2, f(n)=\mathcal{O}(n) \implies \mathcal{O}(n)\))

---

2. 经典模型一：归并分治与逆序对统计

在排序过程中顺便统计“跨越左右两个子区间”的元素配对贡献，是分治算法最经典的题型（如 LeetCode 315、剑指 Offer 51）。

核心思想：

在归并排序的合并阶段，左半区间 \([L, mid]\) 和右半区间 \([mid + 1, R]\) 均已各自有序： * 当左指针指向 \(i\)、右指针指向 \(j\) 且 \(nums[i] > nums[j]\) 时： 由于左半区间升序，左半边从 \(i\) 到 \(mid\) 的所有剩余元素均严格大于 \(nums[j]\)！ * 一步产生 \((mid - i + 1)\) 个逆序对贡献，将逆序对统计从 \(\mathcal{O}(N^2)\) 降至 \(\mathcal{O}(N \log N)\)。

---

3. 经典模型二：平面最近点对 (Closest Pair of Points)

问题：给定二维平面上的 \(n\) 个点，求所有点对中欧氏距离最近的两个点之间的距离。

暴力枚举时间复杂度为 \(\mathcal{O}(N^2)\)。利用分治法可优化至 \(\mathcal{O}(N \log N)\)。

3.1 分治算法全流程

1. 预处理：将所有点按照横坐标 \(x\) 升序排序；
2. 递归分治：
3. 取中线 \(x = mid\_x\)，将点集划分为左右两半；
4. 递归求解左半点集的最近点对距离 \(d_1\)；
5. 递归求解右半点集的最近点对距离 \(d_2\)；
6. 设当前已知最小值 \(d = \min(d_1, d_2)\)。
7. 合并与跨中线检查：
8. 任何距离小于 \(d\) 的新点对，其两个端点必须分别位于中线左右两侧；
9. 横向粗筛：只有到中线的水平距离小于 \(d\) 的点（即 \(|x_i - mid\_x| < d\)）才有可能构成更近的点对；
10. 纵向鸽巢原理精筛：
    • 将横向筛选出的候选点按照纵坐标 \(y\) 排序；
    • 遍历每个点 \(i\)，向后检查纵坐标满足 \(y_j - y_i < d\) 的点 \(j\)；
    • 鸽巢原理核心定理：在尺寸为 \(d \times 2d\) 的矩形区域内，由于左右两侧各自内部的点距均 \(\ge d\)，最多只能容纳 6 个点！
    • 因此，内层循环对每个点至多只需要比对后续 6 个点，合并过程严格在线性 \(\mathcal{O}(N)\) 时间内完成！

#include <vector>
#include <cmath>
#include <algorithm>

struct Point {
    double x, y;
};

double dist(const Point& a, const Point& b) {
    return std::hypot(a.x - b.x, a.y - b.y);
}

double closest_pair_rec(std::vector<Point>& pts, int l, int r) {
    if (r - l <= 3) {
        double min_d = 1e18;
        for (int i = l; i <= r; ++i) {
            for (int j = i + 1; j <= r; ++j) {
                min_d = std::min(min_d, dist(pts[i], pts[j]));
            }
        }
        return min_d;
    }

    int mid = l + (r - l) / 2;
    double mid_x = pts[mid].x;

    double d = std::min(closest_pair_rec(pts, l, mid), closest_pair_rec(pts, mid + 1, r));

    // 筛选位于 [mid_x - d, mid_x + d] 窗口内的点
    std::vector<Point> strip;
    for (int i = l; i <= r; ++i) {
        if (std::abs(pts[i].x - mid_x) < d) {
            strip.push_back(pts[i]);
        }
    }

    // 按纵坐标 y 升序排序
    std::sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
        return a.y < b.y;
    });

    // 鸽巢原理：每个点只需检查纵坐标差值小于 d 的至多 6 个后继点
    int sz = strip.size();
    for (int i = 0; i < sz; ++i) {
        for (int j = i + 1; j < sz && (strip[j].y - strip[i].y) < d; ++j) {
            d = std::min(d, dist(strip[i], strip[j]));
        }
    }
    return d;
}

double closest_pair(std::vector<Point>& pts) {
    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    return closest_pair_rec(pts, 0, pts.size() - 1);
}

---

4. LeetCode 经典真题精选与深度精析

• LeetCode 23 - 合并 K 个升序链表 (Merge k Sorted Lists) 困难

  提示

  分治两两配对合并。

  • 相比于从前往后顺序合并的 \(\mathcal{O}(K^2 N)\) 复杂度，采用分治法两两归并：
  • 每一轮将 \(K\) 个链表两两配对合并为 \(K / 2\) 个链表，递归深度为 \(\mathcal{O}(\log K)\)。
  • 总时间复杂度严格为 \(\mathcal{O}(N \log K)\)。

• LeetCode 315 - 计算右侧小于当前元素的个数 (Count of Smaller Numbers After Self) 困难

  提示

  带索引归并排序（归并分治）。

  • 附带索引数组 indices 进行归并排序。
  • 在合并两半部分时，若左半部分元素大于右半部分元素，右半部分已出队的元素数量即为该元素产生的逆序贡献。
  • 时间复杂度严格 \(\mathcal{O}(N \log N)\)。

• LeetCode 4 - 寻找两个正序数组的中位数 (Median of Two Sorted Arrays) 困难

  提示

  分治折半排除法。

  • 转化为求两个有序数组合并后的“第 \(K\) 小元素”。
  • 每次比对两数组在 \(K/2 - 1\) 位置的数值大小，数值较小的一方的前 \(K/2\) 个元素绝对不可能包含第 \(K\) 小值，直接整段剔除。
  • 递归规模每步缩半，时间复杂度严格 \(\mathcal{O}(\log(M + N))\)。