分治：分解、解决与合并

06-核心算法思想核心预计 20 分钟分治递归设计逆序对

学习状态：

一句话定义

分治（Divide and Conquer）是「分解 → 独立解决子问题 → 合并结果」的三步递归设计框架；其复杂度由递归式 T(n)=a·T(n/b)+f(n) 刻画，可用主定理（kp-003）直接读出。

为什么重要

它是把「大问题变小问题」思想的最系统化版本：归并排序、快速排序、二分查找、快速幂、最近点对、Karatsuba 乘法全部出自这个模板。学分治的价值不在背案例，而在掌握「划分子问题必须独立、合并代价必须可算」这两条适用判据——它们同时划清了分治与动态规划（子问题重叠时）的分界线。

前置知识

kp-003（递归式与主定理）；kp-022（二分作为「只留一半」的退化分治）；递归写法。

核心概念

三步模板：Divide（划分成规模 n/b 的 a 个子问题）、Conquer（递归到基准情形）、Combine（合并子解）。
适用判据：子问题独立（不共享待解决的子状态）⇒ 分治；子问题重叠 ⇒ 该转动态规划。
复杂度来源：a、b 决定树的形状，f(n) 决定每层合并开销，三者共同决定总阶——见 kp-003 三情形。
基准情形：规模足够小（如 n≤1）直接返回，缺失即无限递归。
经典族谱：归并/快排（排序）、二分（查找）、快速幂/O(log n) 求幂、最大子段和、逆序对计数、最近点对、Karatsuba/Strassen（乘法加速）。

直观类比

分治是把一仓库货按「先分四个区、每区各自清点、最后把四份清单合并」的流程组织人手：分区（分解）互不干扰（独立），汇总清单（合并）只花一点点时间。若各区之间频繁借货，这套流程就失灵——那是「重叠子问题」，得换 DP 的总账本。

原理与机制

逆序对计数（分治思想的最佳示范，也是归并排序的复用）：

函数 count(lo, hi):            // 返回区间内逆序对数并排序该区间
    若 hi − lo ≤ 1: 返回 0
    mid ← (lo + hi) / 2
    ans ← count(lo, mid) + count(mid, hi)
    合并两有序半段时:
        若取左半元素则无贡献
        若取右半元素则贡献 「左半剩余元素个数」 个逆序对
    返回 ans
T(n) = 2T(n/2) + O(n) ⇒ Θ(n log n)，把暴力 O(n²) 压掉一个 n。

要点：合并阶段「顺便」完成了跨中线的统计——好的分治设计常让 Combine 免费携带答案信息。

公式或模型

快速幂：a^n = (a^(n/2))²（n 偶）或 (a^(n/2))²·a（n 奇），T(n)=T(n/2)+Θ(1)=Θ(log n)；对模 m 运算是 RSA 类大数计算基元。
最大子段和三分量：ans = max(左半 ans, 右半 ans, 跨中线的最大前后缀之和)，T(n)=2T(n/2)+O(n)=Θ(n log n)。
最近点对：按 x 排序后只检查中线 ±δ 条带内的点（按 y 排序后每点至多比 7 个），T(n)=2T(n/2)+O(n)=Θ(n log n)。

图示

分治递归树（归并排序型）:
             n              ← 合并代价 n
           /   \
          n/2   n/2         ← 每层合计 n
         /  \  /  \
        n/4 …   …          ← 共 log₂n 层
总代价 = n × log₂n
逆序对同型，仅合并函数多带回一个计数。

实例或案例

归并排序（kp-020）与逆序对：同一框架两次收割。
Karatsuba 大数乘法：把 O(n²) 竖式乘法改为 3 次 n/2 位乘法，T(n)=3T(n/2)+O(n)=Θ(n^log₂3)≈Θ(n^1.585)。
求数组中「只出现一次的数」的分组变体、竞赛中的平面最近点对。
MapReduce 时代的大规模归并：分片（divide）→ 各 worker 求解 → reduce 合并，正是分治的系统级放大。

常见误区

子问题不独立仍硬套分治（如带依赖的最优划分）：得到错误答案或指数重复，应转 DP（kp-026）。
合并代价漏算或估错：主定理情形选错，复杂度判断全盘皆错。
基准情形缺失或边界含糊（mid 偏左偏右），导致死递归或漏算一半区间。
以为「能递归就算分治」：真正的设计难点在 Divide 划法与 Combine 算法，不在递归本身。

自测题

用分治 + 归并描述求逆序对的算法，并写复杂度。

答案要点：见机制节；合并时右半元素出列贡献左半剩余数，T(n)=2T(n/2)+Θ(n)=Θ(n log n)。

快速幂求 a¹⁰ mod m 的递归展开路径是什么？

答案要点：a¹⁰=(a⁵)²，a⁵=(a²)²·a，a²=(a)²·a——共 O(log n) 次乘法。

「求第 k 小」能否分治？给出思路与复杂度。

答案要点：快选（quickselect）：partition 后只递归含 k 的一侧，T(n)=T(n/b)+O(n) 期望 O(n)，是「只留一半」的分治。

与其他知识点的关系

kp-003 提供分析工具；kp-020 是最大应用族；kp-026 划清「重叠子问题转 DP」的边界；kp-022 二分是它「只递归一侧」的退化形态。

延伸阅读

《算法导论》第 4 章；《算法设计》第 5 章（含 VLSI 芯片测试等非常规案例）。