📚 分治策略详解：从归并排序到 Strassen 矩阵乘法
英文标题 / English Title: Divide and Conquer in Depth: From Merge Sort to Strassen’s Matrix Multiplication
来源 / Source: 算法导论 & 泊松不粘人
📌 文章简介 / Introduction
分治是算法设计中最强大的策略之一。本文通过归并排序、Karatsuba 乘法、Strassen 矩阵乘法等多个经典案例，深入剖析分治的思想本质，以及如何分析分治算法的时间复杂度。
Divide and Conquer is one of the most powerful strategies in algorithm design. This article uses Merge Sort, Karatsuba multiplication, Strassen’s algorithm, and other classics to deeply analyze the essence of divide and conquer and how to analyze its time complexity.
👉 阅读原文: 分治策略详解
🔍 内容要点 / Key Points
1. 分治 vs 减治 vs 变治
算法设计三大策略：
- 分治 (Divide and Conquer)：分解 → 求解 → 合并（如归并排序）
- 减治 (Reduce and Conquer)：原问题分解为一个子问题（如二分查找）
- 变治 (Transform and Conquer)：先变换问题形式再求解（如哈希表）
2. Master 定理 —— 分治复杂度分析神器
对于形如 T(n) = aT(n/b) + f(n) 的递归式：
| 条件 | 结果 |
|---|---|
| f(n) = O(n^log_b(a-ε)) | T(n) = Θ(n^log_b(a)) |
| f(n) = Θ(n^log_b(a) · log^k(n)) | T(n) = Θ(n^log_b(a) · log^(k+1)(n)) |
| f(n) = Ω(n^log_b(a+ε)) 且正则条件 | T(n) = Θ(f(n)) |
3. 分治的三个注意点
- 子问题要平衡：子问题规模尽量相等（如归并排序的中点分割）
- 合并代价要低：如果合并代价过高，可能不如直接求解
- 递归深度控制：深度过深会导致栈溢出，需要改写为迭代
4. 经典应用拓展
| 问题 | 分治策略 | 复杂度 |
|---|---|---|
| 棋盘覆盖 | 分割为4个子棋盘 | O(4^k) |
| 循环赛 | 分治成两半 | O(n log n) |
| 求逆序对 | 归并排序中计数 | O(n log n) |
💡 学习建议 / Learning Tips
- 从排序入门：归并排序是理解分治最好的起点，把排序过程想清楚再学其他应用。
- 手写递归树：用递归树法手推复杂度，比记公式更直观。
- Master 定理要会用：推导出来的公式可以用 Master 定理验证，双重保险。
- 注意合并时机：不是所有分治都需要显式合并，有些问题在分解时就能得到答案。
- 与DP对比学习：分治分解后子问题重叠就变成了动态规划，理解边界很重要。
| *本文由 AI 自动生成 | Generated by AI* |