分治：从归并排序到最近点对

0. 元信息

• 主题路径：docs/topics/algo-design/subtopics/divide-and-conquer/README.md
• 父主题：algo-design
• 主分类：数据结构与算法
• 辅助分类：计算机基础
• 适合对象：掌握递归与复杂度分析；想理解算法复杂度推导和分治思维的学习者
• 建议周期：2～3 周（每周 10～14 小时）
• 前置知识：recursion-and-backtracking、基础几何 / 概率、Python 列表切片
• 最终目标：能独立写出归并排序、快排、计数逆序对、最近点对；能用 Master Theorem 推导常见 T(n)；能在面试中讲清 merge 与 partition 的差异

1. 学习路线

分治范式：分解 → 解决 → 合并
  → 归并排序（含计数逆序对）
  → 快速排序与 partition（Hoare / Lomuto）
  → 主定理（Master Theorem）三种情况
  → 二分查找与二分答案
  → 最近点对（Closest Pair）
  → 大整数乘法 / Strassen
  → 棋盘覆盖 / CDQ 分治

每一步都推 T(n)。归并排序是分治的”教科书级”案例。

2. 阶段周数分配

每天 1.5～2 小时。2 周方案聚焦前 5 阶段；3 周方案多一周做最近点对与 Strassen。

3. 九阶段表（精简）

3.1 核心知识

• 分治三步：分解（divide）、解决（conquer）、合并（combine）。
• 递推式：T(n) = a·T(n/b) + f(n)；a 是子问题数，b 是规模缩小比，f(n) 是合并代价。
• Master Theorem 三种情况：f(n) 相对 n^(log_b a) 的增长决定 T(n)。
• 归并排序：分解到底再合并；空间 O(n)（非原地）。
• 快速排序：原地 partition；期望 O(n log n)，最坏 O(n²)（基准选择）。
• 二分查找：分治的”不均匀”版本；T(n) = T(n/2) + O(1) = O(log n)。
• 最近点对：分治 + 跨带扫描的 7 点优化。

3.2 实践产出

• 复述 / 手写：归并排序、快排（含 Hoare / Lomuto 两种 partition）、二分查找（递归与迭代）、计数逆序对、pow(x, n)、最大子数组和（Kadane + 分治）；
• 4 道进阶题：LeetCode 4 寻找两个有序数组的中位数、LeetCode 23 合并 K 个升序链表、LeetCode 315 计算右侧小于当前元素的个数、LeetCode 327 区间和的个数；
• 1 道经典题：最近点对（用分治实现 O(n log n)）。

3.3 可观察学会标准

• 不看答案在 15 分钟内写出归并排序与快排；
• 能推导归并排序 T(n) = 2T(n/2) + O(n) = O(n log n)；
• 能解释为什么快排最坏 O(n²)（已排序数组 + 选首元素作 pivot）；
• 能在 40 分钟内独立实现最近点对的 O(n log n) 算法（含 7 点扫描）。

4. 第一周（每天 1.5~2 小时）

Day 1 约定：本计划使用 Python 3.10+。统一格式：python -X dev -W error -m py_compile foo.py；测试用 pytest。所有代码放进 algo-design/divide-conquer/week<N>/ 目录；每个题目单独 .py 文件，配套 notes/<problem>.md 含递推式 T(n) 推导、递归树图、Master Theorem 验证。

Day 7 执行次序

步骤 A —— 归并排序完整版（60~90 分钟）

1. 写 merge_sort(arr)；
2. 写递推式 T(n) = 2T(n/2) + O(n)；
3. 用 Master Theorem 解 T(n) = O(n log n)；
4. 画递归树标每层代价；
5. 跑 n=10, 100, 1000, 10000 测耗时，画 n-log(n) 曲线。

步骤 B —— 4 类边界用例（30~45 分钟）

Day 7 当天必完成步骤 A；步骤 B 至少完成 B1、B4。

5. 阶段通用验收（精简）

1. 不看答案重写归并 / 快排 / 二分 / 逆序对 / 最近点对；
2. 用自己的话解释 Master Theorem 三种情况；
3. 画出归并 / 快排的递归树，标出每层代价；
4. 测试 n=0, 1, 2, 100, 10000 五档；
5. 至少准备 3 组自定义数据贴出实际输出；
6. 记录每题时间空间复杂度；
7. 能修改算法（换 pivot、加随机化、并行化）并解释影响。

6. 最终验收

• 独立实现：归并排序（含计数逆序对）、快速排序（Hoare + Lomuto partition）、二分查找（递归 + 迭代 + 二分答案）、最近点对（含 7 点扫描）、最大子数组和（Kadane + 分治）；

• 至少完成 14 道题（LeetCode / CSES / AtCoder），分布建议：

  子阶段	题目数量	难度分布	平台建议
  归并排序与逆序对	3 道	2 Easy + 1 Medium	LeetCode 912 + CSES Counting Inversions + LeetCode 315
  快速排序与 partition	2 道	2 Easy	LeetCode 912 + 排序稳定性练习
  二分查找与二分答案	3 道	2 Easy + 1 Medium	LeetCode 34 + 410 + 658
  最大子数组和	2 道	1 Easy + 1 Medium	LeetCode 53 + 918
  进阶分治	4 道	2 Medium + 2 Hard	LeetCode 4 + 23 + 327 + 最近点对

  约束：至少 5 道达到 Medium，至少 2 道达到 Hard；归并 / 快排必须能在 15 分钟内重写。

• 完成 1 个综合 Python 项目（自带 README，能被他人按文档复现）；

• 能用 15 分钟讲清分治三步、Master Theorem 三种情况、归并 vs 快排的合并代价、pivot 策略对复杂度的影响、最近点对 7 点扫描的来源。

7. 综合项目

首选：分治算法可视化工具（必做：CLI 输入 + 输出 + 可选 GUI）。
备选：归并 / 快排对比器（输入 n → 跑两种排序 → 输出耗时曲线 + 稳定性 + 空间占用）。
备选：最近点对求解器（输入平面点集 → 输出最近距离 + 可视化 + 7 点扫描动画）。

分治算法可视化工具必做要求：

• 输入：stdin 接收算法名（merge_sort / quick_sort / closest_pair / max_subarray / binary_search）+ 数据集；
• 输出：必输出（1）算法过程的文字回放（每一步状态、当前下标、做了什么操作）；（2）时间 / 空间复杂度 + 实际耗时；（3）递推式 T(n) + Master Theorem 解；（4）递归树每层代价（节点数 × 单节点代价）；
• 算法：必须用至少 3 种范式（递归 + 分治 + 二分）；
• 进阶可选：ASCII 动画（终端 curses 逐步展开）、matplotlib 画递归树 GUI、可对比两种 partition 策略的可视化。

任何综合项目都必须包含：

1. 需求说明（含输入输出约定）；
2. 数据结构与算法选择理由（为何用分治、为何选这种 partition）；
3. 核心模块说明（Solver / Recorder / Renderer 三层）；
4. 模块化源码（每题单独文件 + 公共 base class）；
5. 边界测试（n=0, 1, 2, 100, 10000 + 已排序 + 全逆序）；
6. 运行说明（Makefile 或清晰的 python -m 命令）；
7. README（项目介绍、运行步骤、目录结构、复盘）；
8. notes/ 规范：

本主题贡献

3 职责

1. 把”分解 / 解决 / 合并”形式化为递推式 T(n) = a·T(n/b) + f(n) —— 数清子问题数 a、规模缩小比 b、合并代价 f(n)，并对照 Master Theorem 三种情况（f(n) ≪ / ≈ / ≫ n^(log_b a)）得到 T(n) 的渐近复杂度。
2. 区分归并与快排的合并代价 —— 归并排序稳定 O(n log n) 但需 O(n) 辅助空间（非原地），快排原地但最坏 O(n²)；pivot 选首元素遇到已排序数组必退化，必须用随机化或三数取中（introsort 思路）。
3. 把二分查找扩展为二分答案（写”判定函数” → 在单调区间上二分搜索），用分治实现最近点对的 O(n log n) 含跨带 7 点扫描 —— 鸽巢原理保证中线两侧各点只需与对侧固定常数个邻居比较，证明 7 已是最紧的常数。

4 交付物

1. 14 道题解（归并 / 快排 / 二分 / 计数逆序对 / 最大子数组和 / 最近点对）+ 4 类边界用例日志（n=0 空 / n=1 单元素 / 已排序 / 全逆序）。
2. 分治可视化工具（CLI → 递推式 T(n) + Master Theorem 解 + 递归树每层代价 + 实际耗时曲线，画归并 / 快排 / 二分 / 最近点对四类）。
3. Master Theorem 6 道递推式求解表 notes/master-theorem.md（2T(n/2)+O(n) / 2T(n/2)+O(1) / 4T(n/2)+O(n²) / 2T(n/2)+O(n²) / T(n/2)+O(1) / 4T(n/2)+O(n)，每道标 log_b(a) 与 f(n) 增长阶比较） + 至少 3 题（归并 / 快排 / 二分）的递归树 DOT 文件。
4. pivot 策略对比表 notes/pivot-comparison.md（首元素 / 随机 / 三数取中在 n=1000 已排序数组上的耗时差距，验证退化防御）。

3 指标

1. 15 分钟内不看答案重写归并 / 快排（含 Hoare / Lomuto 两种 partition，覆盖分治范式两个最经典的排序实现）。
2. 在 n=10 / 100 / 1000 / 10000 上画出实际耗时 vs n·log(n) 对比曲线，验证 T(n) = O(n log n)（从实测数据反推理论复杂度，证明”复杂度分析”已可量化）。
3. 40 分钟内独立实现最近点对的 O(n log n) 含 7 点扫描（鸽巢原理 + 中线 y 排序的工程实现，几何分治的巅峰案例）。

许可证提示：CLRS 与 Manber 自用学习合理引用；不要复制粘贴 CLRS 课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。CSES 题面公开。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先用 Roughgarden 第 2 册建立分治直觉 → 手写归并 / 快排 + 推 T(n) → 用 Master Theorem 验 → 选读 CLRS 第 4 章 → 用 LeetCode 刷 6 道分治题 → 跑 CSES 排序与搜索章节 → 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 实现最近点对 → 选读 Strassen 1969 论文 → 写复盘到 notes/retrospective.md。

8. 推荐开源资料

许可证提示：CLRS 与 Manber 自用学习合理引用；不要复制粘贴 CLRS 课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。CSES 题面公开。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先用 Roughgarden 第 2 册建立分治直觉 → 手写归并 / 快排 + 推 T(n) → 用 Master Theorem 验 → 选读 CLRS 第 4 章 → 用 LeetCode 刷 6 道分治题 → 跑 CSES 排序与搜索章节 → 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 实现最近点对 → 选读 Strassen 1969 论文 → 写复盘到 notes/retrospective.md。

9. 学习资料汇聚（v0.3）

9.1 背景与动机

分治思想可追溯到 1840 年代 Gauss 的大数乘法思想；Hoare 在 1959 年发明快速排序，奠定了分治在排序里的核心地位；Strassen 在 1969 年用分治把矩阵乘法从 O(n³) 降到 O(n²·log₂7) ≈ O(n^2.81)，这是分治范式最具冲击力的结果。CLRS 把 Master Theorem 形式化成了 4 版教材里的”必学章节”。

行业位置：分治是排序、搜索、FFT、CDQ 分治的基础。算法面试常考”写出归并 / 快排 + 解释复杂度”。竞赛里 FFT / CDQ 是高级选手的工具。一句话总结：分治 = 把问题拆成互不重叠的子问题，最后合并答案。

9.2 概念地图

flowchart LR
  Divide[分解]
  Conquer[解决子问题]
  Combine[合并]
  MergeSort[归并排序]
  QuickSort[快速排序]
  BinarySearch[二分查找]
  InversionCount[计数逆序对]
  ClosestPair[最近点对]
  Strassen[Strassen 矩阵乘]
  Master[主定理]
  Recurrence[递推式]

  Divide --> Conquer --> Combine
  MergeSort --> Divide
  QuickSort --> Divide
  BinarySearch --> Divide
  InversionCount --> MergeSort
  ClosestPair --> Divide
  Strassen --> Divide
  Master --> Recurrence
  Recurrence --> MergeSort
  Recurrence --> QuickSort
  Recurrence --> ClosestPair

核心关系：分治三步是底座；归并 / 快排 / 二分是三个最常见实例；Master Theorem 把复杂度推导形式化；最近点对是分治 + 跨带优化的巅峰案例。

9.3 基础知识讲解

9.3.1 经典论文

9.3.2 经典书籍

9.3.3 优秀博客

9.3.4 核心人物

9.3.5 开发方法

9.4 经典问题与经典案例

9.5 学习难点

概念难点

思维难点

工程难点

9.6 技术标准与接口

9.6.1 Entity

9.6.2 Scope

• 分治适用：排序、搜索、FFT、最近点对、大整数乘、CDQ 分治。
• 不适用：图最短路（用 BFS / Dijkstra）；最大流；NP-hard 无多项式解。
• 与 DP 的区别：分治的子问题不重叠（merge sort）；DP 的子问题可能重叠（LCS）。

9.6.3 Structure

• 必须掌握的方法：写 T(n) 递推式；用 Master Theorem 验；画递归树；选 pivot 策略。
• 必须掌握的 API：bisect.bisect_left / bisect_right（二分插入）；heapq.merge（多路归并）。

9.6.4 Ecosystem

• 工具：bisect（二分）、heapq（优先队列）、numpy.fft（FFT）。
• 在线评测：LeetCode、AtCoder、Codeforces、CSES。
• 训练集：CSES Sorting and Searching、USACO Guide 分治模块。

9.6.5 Depth Tiers

本子主题目标：L3。能写归并 / 快排 + 推导 T(n) + 实现最近点对即达到。

9.6.6 Source

• CLRS 官网：第 4 版第 4 章。
• CP-Algorithms Divide and Conquer：模板与例题。
• CSES Problem Set：分治题集合。
• 引用版本快照日期：2026-07-30。

10. 常见误区

• 写归并排序时忘记合并时的拷贝，导致原地修改输入数组；
• 快排的 pivot 选首元素，遇到已排序数组退化到 O(n²)；
• 二分查找的边界写错（left < right vs left <= right），死循环或漏解；
• 写递推式算错子问题数或合并代价；
• 用 Master Theorem 套错（f(n) 与 n^(log_b a) 比错）；
• 最近点对的 7 点扫描写成 8 点或更多，复杂度退化；
• 浮点比较用 ==，应该用 < EPS；
• CDQ 分治忘了离散化或排序；
• 二分答案时把”判定函数”写成线性，复杂度退化；
• 写完不复盘，下周遇到同类型还是不会。

11. 所有知识点分类

1. 编程语言（辅）：Python 列表切片与拷贝、bisect.bisect_left / bisect_right 做二分、heapq.merge 做多路归并、functools.lru_cache 做递归 memo、递归迭代化与 sys.setrecursionlimit。
2. 数据结构与算法（主）：分治三步（分解 / 解决 / 合并）、递推式 T(n) = a·T(n/b) + f(n)、Master Theorem 三种情况、归并排序（含计数逆序对）、快速排序（Hoare / Lomuto partition、pivot 随机化）、二分查找（递归 / 迭代 / 二分答案）、最近点对（分治 + 跨带 7 点扫描）、Strassen 矩阵乘、FFT、CDQ 分治。
3. 计算机基础：递归与递推式、Master Theorem 形式化证明、鸽巢原理（最近点对 7 点来源）、浮点精度与 EPS。
4. 工程技术：画递归树并标每层代价、pivot 策略对比（首元素 / 随机 / 三数取中）、外部排序的 cache-friendly 合并、n × 2^n 状态数估算与算法选型。
5. Web 与后端：无直接关联。
6. 前端与客户端：无直接关联。
7. 数据与人工智能：FFT 可作为信号处理基础；本计划不展开。
8. 项目与职业能力：LeetCode 4 / 23 / 315 / 327 等分治面试题、15 分钟重写归并 / 快排、40 分钟实现最近点对 O(n log n)。

本计划归属：数据结构与算法 主 + 编程语言 辅。