12.1 分治回顾：把大问题切成小块

核心问题：如何拆解大问题为相似小问题？
直觉：像切蛋糕——把大蛋糕切成小块，每个人吃自己的那份，最后大家都能吃饱。

一、问题情境：如何高效排序一个大数组？

想象你是一个图书管理员，面前有100万本书，需要按书名排序。

朴素方案：你一本一本看，每次找最小的那本放前面。

python

# 朴素方案：选择排序
def naive_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

这个方案时间复杂度是O(n²)——100万本书需要10万亿次比较！

思考：有没有更快的方法？

一个聪明的想法浮现了：不要一个人排序所有书，而是分给两个人，每人排一半，再合并结果。

这就是分治思想的萌芽。

二、直觉引入：切蛋糕的艺术

2.1 什么是分治？

**分治（Divide and Conquer）**的核心直觉是：

把大问题切成几个相似的小问题，分别求解，再把结果合并成大问题的解。

想象你在切蛋糕：

切（Divide）：把大蛋糕切成若干块
吃（Conquer）：每个人吃自己那块
拼（Combine）：不需要拼——大家吃饱了就行

但算法里的"切蛋糕"更复杂：切开后需要拼回去。

2.2 分治三步法

分治三阶段：
┌─────────────┐
│ 1. Divide   │  分解：将问题分解为 k 个子问题
├─────────────┤
│ 2. Conquer  │  求解：递归求解子问题（或直接求解小问题）
├─────────────┤
│ 3. Combine  │  合并：合并子问题的解
└─────────────┘

关键：子问题必须独立——不能有重叠依赖。

2.3 为什么"独立"这么重要？

如果子问题有重叠，分治会重复计算——效率极低。

例子：斐波那契数列的递归实现

python

# 分治思路的斐波那契（问题！）
def fib_divide(n):
    if n <= 1:
        return n
    # 分解：fib(n) = fib(n-1) + fib(n-2)
    # 但这两个子问题有重叠！
    return fib_divide(n-1) + fib_divide(n-2)  # O(2^n)！

问题：fib(5) 计算 fib(4)+fib(3)，而 fib(4) 又计算 fib(3)+fib(2)，fib(3)被重复计算了！

这就是分治的禁忌——子问题重叠时，应该用动态规划（见12.3节）。

三、算法定义：分治形式化

3.1 分治的递推方程

分治算法的时间复杂度可以用递推方程表示：

T(n) = k·T(n/k) + f(n)

其中：
k：子问题个数（通常k=2）
n/k：子问题规模
f(n)：合并成本

例子：归并排序

T(n) = 2·T(n/2) + O(n)

解释：
- 分成两半：k=2
- 每半规模：n/2
- 合并两半：O(n)（需要比较和复制）

3.2 主定理（Master Theorem）

对于形如 T(n) = aT(n/b) + f(n) 的递推方程，有三种情况：

情况	条件	复杂度结果	解释
Case 1	f(n) = O(n^(log_b a - ε))	T(n) = Θ(n^log_b a)	子问题成本占主导
Case 2	f(n) = Θ(n^log_b a)	T(n) = Θ(n^log_b a · log n)	成本相当
Case 3	f(n) = Ω(n^(log_b a + ε))	T(n) = Θ(f(n))	合并成本占主导

应用：归并排序属于Case 2

T(n) = 2T(n/2) + n
a=2, b=2 → log_b a = log_2 2 = 1
f(n) = n = Θ(n^1) → Case 2
结果：T(n) = Θ(n log n)

四、实现示例：归并排序教学化代码

4.1 归并排序完整实现

python

def merge_sort(arr):
    """
    归并排序：分治思想的经典实现
    
    思路：
    1. Divide：将数组分成两半
    2. Conquer：递归排序两半
    3. Combine：合并两个有序数组
    """
    # 基础情况：数组长度≤1时已有序
    if len(arr) <= 1:
        return arr
    
    # Divide：分成两半
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Conquer：递归排序两半
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # Combine：合并两个有序数组
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """
    合并两个有序数组
    
    复杂度：O(len(left) + len(right))
    """
    result = []
    i = j = 0
    
    # 比较并合并
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

# 测试
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # [3, 9, 10, 27, 38, 43, 82]

4.2 代码背后的分治思想

代码段	对应分治步骤
`mid = len(arr) // 2`	Divide：分解位置
`left = arr[:mid]`	Divide：切分左半
`right = arr[mid:]`	Divide：切分右半
`merge_sort(left)`	Conquer：递归求解左半
`merge_sort(right)`	Conquer：递归求解右半
`merge(left, right)`	Combine：合并结果

五、复杂度分析：时间与空间

5.1 时间复杂度

归并排序：O(n log n)

计算过程（主定理）：
T(n) = 2T(n/2) + O(n)

递归树分析：
Level 0: 1个问题，成本 n
Level 1: 2个问题，成本 n/2 + n/2 = n
Level 2: 4个问题，成本 n/4 × 4 = n
...
Level log n: n个问题，成本 1 × n = n

总层数：log n
每层成本：n
总成本：n × log n = O(n log n)

对比朴素方案：

算法	时间复杂度	100万数据耗时
选择排序（朴素）	O(n²)	~10万亿比较（天文数字）
归并排序（分治）	O(n log n)	~20万次比较（秒级）

分治让效率提升5个数量级！

5.2 空间复杂度

归并排序：O(n)（需要临时数组存储合并结果）

空间使用：
- 递归栈：O(log n)
- 合并临时数组：O(n)
总计：O(n)

改进：原地归并排序可以将空间降到O(1)，但实现复杂。

六、与前章节关联：分治在哪里出现过？

6.1 分治前章节应用

章节	分治应用	说明
Ch3	归并排序、快速排序	分治的经典应用
Ch3	二分查找	分治的特殊情况（只处理一半）
Ch4	图的连通分量	BFS/DFS可视为分治
Ch7	最小生成树（Kruskal）	按边分治（贪心分治结合）
Ch9	MapReduce	分布式分治的工业应用

6.2 快速排序：另一种分治

归并排序 vs 快速排序：

维度	归并排序	快速排序
分解策略	固定切成两半	按pivot分成大小两区
合并步骤	需要（合并有序数组）	不需要（已原地排序）
空间复杂度	O(n)	O(log n)（递归栈）
最坏情况	O(n log n)	O(n²)（pivot选择不当）
平均情况	O(n log n)	O(n log n)

快速排序的直觉：

不像归并排序的"切→排→拼"，快速排序是"选基准→分区→递归"：
1. 选一个pivot（基准）
2. 小的放左边，大的放右边（分区）
3. 递归排序左右两区
4. 无需合并——已经有序了

七、设计反思：分治的失败案例

7.1 失败案例1：最长递增子序列（LIS）

问题：给定数组，找最长递增子序列的长度。

错误分治尝试：

python

# 错误的分治思路
def lis_divide(arr):
    if len(arr) <= 1:
        return len(arr)
    
    mid = len(arr) // 2
    left_lis = lis_divide(arr[:mid])
    right_lis = lis_divide(arr[mid:])
    
    # 问题：如何合并？
    # 后半段的LIS可能从前半段的某个元素开始！
    # 子问题不独立，无法简单合并
    return ???  # 无法正确合并

失败原因：子问题不独立

例子：arr = [1, 3, 2, 5, 4, 6]

分成两半：
左半：[1, 3, 2] → LIS = 2 ([1, 3])
右半：[5, 4, 6] → LIS = 2 ([5, 6] 或 [4, 6])

合并问题：
[1, 3] + [5, 6] = [1, 3, 5, 6] 长度4？是的！
但 [1, 2] + [4, 6] = [1, 2, 4, 6] 长度也是4
而且 [1, 2] + [5, 6] = [1, 2, 5, 6] 也能合并

问题：后半段的LIS可能从前半段的不同元素开始
→ 无法确定如何正确合并
→ 分治失败

正确解法：动态规划（见12.3节）

python

def lis_dp(arr):
    """
    LIS的DP解法
    
    状态：dp[i] = 以arr[i]结尾的最长递增子序列长度
    转移：dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
    """
    n = len(arr)
    dp = [1] * n  # 每个元素至少能组成长度1的子序列
    
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

7.2 失败案例2：最短路径问题

问题：给定图，找从起点到终点的最短路径。

错误分治尝试：

思路：把路径分成两段
起点→中间点 + 中间点→终点

问题：
1. 中间点选择不当 → 路径非最优
2. 子问题相互依赖（中间点影响两边）
3. 合并复杂（需要枚举所有中间点）

正确解法：贪心（Dijkstra）或DP（Bellman-Ford）

算法	适用场景	复杂度
Dijkstra（贪心）	无负边图	O(V²) 或 O(V log V + E)
Bellman-Ford（DP）	可有负边（无负环）	O(VE)
Floyd-Warshall（DP）	所有节点间最短路径	O(V³)

7.3 失败总结：分治的三禁忌

禁忌	现象	正确范式
子问题不独立	子问题有重叠依赖	动态规划
合并成本过高	合并步骤比子问题求解还复杂	换分解策略
无法有效分解	找不到自然的分解方式	贪心或回溯

八、知识卡片

C12-01 分治三步法

直觉解释：像切蛋糕，把大问题切成小块分别处理，再把结果拼起来。

核心内容：

步骤	名称	作用
1	Divide	将问题分解为 k 个子问题
2	Conquer	递归求解子问题（或直接求解小问题）
3	Combine	合并子问题的解

关键特征：子问题必须相互独立，不能有重叠依赖。

常见误解：

❌ 分治总是高效的——错！如果合并成本过高，反而更慢
✅ 正确理解：分治效率取决于分解策略和合并复杂度

实例：归并排序（分解数组、分别排序、合并有序数组）。

C12-02 递归树分析

直觉解释：像画家谱树，每层代表一次递归调用，算清总工作量。

核心内容：Master Theorem 主定理解决 T(n) = aT(n/b) + f(n) 形式。

关键特征：

分叉数 a：子问题个数
缩小比例 b：子问题规模缩小倍数
合并成本 f(n)：合并步骤的复杂度

常见误解：

❌ 递归深度等于时间复杂度——错！要看总节点数
✅ 正确理解：时间复杂度 = 每层工作量 × 层数

实例：归并排序 T(n) = 2T(n/2) + O(n)，总复杂度 O(n log n)。

C12-03 分治正确性

直觉解释：分治的正确性依赖于三个条件成立。

核心内容：

子问题独立（无交叉依赖）
合并有效（正确组合结果）
基础正确（边界情况）

关键特征：数学归纳法证明——基础正确 + 假设子问题正确 + 证明合并正确。

常见误解：

❌ 合并总是简单的——有些问题合并步骤极其复杂
✅ 正确理解：合并步骤的设计是分治成败的关键

实例：归并排序正确性：两个有序数组合并后仍有序（可用循环不变式证明）。

C12-04 分治 vs 贪心

直觉解释：分治是"先分再治"，贪心是"步步为营"。

核心内容：

维度	分治	贪心
思路	先分解，后合并	每步选当前最优
适用条件	子问题独立可合并	局部最优→全局最优
结果保证	保证全局最优（正确合并）	不一定全局最优（需证明）

关键特征：分治和贪心适用的条件完全不同。

常见误解：

❌ 分治和贪心可以混用——它们的适用条件互斥
✅ 正确理解：分治需要"独立分解"，贪心需要"无后效性"

实例：排序用分治（归并排序）；最短路径用贪心（Dijkstra）。

C12-05 分治 vs DP

直觉解释：分治是"一题一解"，DP是"一题多解后缓存"。

核心内容：

维度	分治	DP
子问题关系	独立无重叠	重叠需缓存
空间使用	无需记录中间结果	用表格记录
适用场景	无重复计算	有重复计算

关键特征：分治不记录中间结果；DP用表格记录避免重复计算。

常见误解：

❌ 分治和DP可以互相转换——只有子问题重叠时才转DP
✅ 正确理解：DP是分治的优化（当子问题重叠时）

实例：斐波那契——分治递归 O(2^n)；DP 缓存 O(n)。

C12-06 分治失败案例

直觉解释：有些问题看似能分治，实则分治后更糟。

核心内容：失败原因：

子问题不独立
合并成本过高
无法有效分解

关键特征：强行分治会导致效率下降甚至无法正确求解。

常见误解：

❌ 任何问题都能分治——错！必须验证三条件
✅ 正确理解：分治适用有严格条件

实例：

最短路径问题——分治后合并成本极高（不如贪心或DP）
LIS问题——子问题不独立（应改用DP）

C12-07 并行分治

直觉解释：把蛋糕切成块，多人同时吃，效率倍增。

核心内容：分治天然适合并行——子问题独立可同时求解。

关键特征：MapReduce 框架的思想源头：

Map = Divide + Conquer
Reduce = Combine

常见误解：

❌ 并行分治能解决任何问题——合并步骤仍需串行，可能成为瓶颈
✅ 正确理解：并行分治的瓶颈在合并

实例：MapReduce 词频统计（分片统计 → 合并计数）。

C12-08 分治直觉建立

直觉解释：看到"大问题可拆成相似小问题"，先想分治。

核心内容：判断分治适用的三个直觉问题：

能否分解？
子问题独立？
能否合并？

关键特征：抓住"相似结构递归"的本质，不是简单的"分成小块"。

常见误解：

❌ 分治就是递归——错！关键在于分解策略和合并方法
✅ 正确理解：分治 = 分解策略 + 递归求解 + 合并方法

实例：快速排序的直觉——选基准分成大小两堆，递归排序，无需合并（已就位）。

九、练习设计

基础练习（理解分治）

练习 12.1-1：用分治思路解释二分查找。

提示：

二分查找可以看作分治的特殊情况：
- Divide：分成两半（但只处理一半）
- Conquer：递归查找目标所在的一半
- Combine：无需合并（直接返回结果）

练习 12.1-2：计算以下递推方程的复杂度：

T(n) = 3T(n/4) + n²

答案：

a=3, b=4 → log_b a = log_4 3 ≈ 0.79
f(n) = n² = Ω(n^0.79 + ε) → Case 3
结果：T(n) = Θ(n²)

进阶练习（分治应用）

练习 12.1-3：设计分治算法计算数组中第k大的元素。

思路：

1. 选一个pivot
2. 分区：小的放左，大的放右
3. 判断pivot位置：
   - pivot位置 = k → 返回pivot
   - pivot位置 > k → 在左半找第k大
   - pivot位置 < k → 在右半找第(k - pivot位置 - 1)大
4. 平均复杂度：O(n)

设计练习（分治 vs DP）

练习 12.1-4：分析"最大子数组问题"为何能用分治，但更推荐用DP。

分析：

分治思路：
- Divide：分成两半
- Conquer：找左半最大子数组、右半最大子数组
- Combine：还要找跨越中间的最大子数组（额外工作）
- 复杂度：O(n log n)

DP思路：
- 状态：dp[i] = 以i结尾的最大子数组
- 转移：dp[i] = max(arr[i], dp[i-1] + arr[i])
- 复杂度：O(n)

DP更优！因为子问题重叠（dp[i]依赖dp[i-1]）

开放练习

练习 12.1-5：LLM的注意力矩阵计算（矩阵乘法）如何体现分治思想？

思考方向：

Transformer的注意力：
Attention(Q, K, V) = softmax(QK^T / sqrt(d)) V

QK^T 是矩阵乘法，可以用分治加速：
- Divide：矩阵分块
- Conquer：分块矩阵乘法
- Combine：组合结果

Strassen矩阵乘法：O(n^2.807) 优于朴素O(n³)
这是分治在高维数据上的应用

导航：上一节：章节导览 | 下一节：12.2 贪心回顾 →

12.1 分治回顾：把大问题切成小块 ​

一、问题情境：如何高效排序一个大数组？ ​

二、直觉引入：切蛋糕的艺术 ​

2.1 什么是分治？ ​

2.2 分治三步法 ​

2.3 为什么"独立"这么重要？ ​

三、算法定义：分治形式化 ​

3.1 分治的递推方程 ​

3.2 主定理（Master Theorem） ​

四、实现示例：归并排序教学化代码 ​

4.1 归并排序完整实现 ​

4.2 代码背后的分治思想 ​

五、复杂度分析：时间与空间 ​

5.1 时间复杂度 ​

5.2 空间复杂度 ​

六、与前章节关联：分治在哪里出现过？ ​

6.1 分治前章节应用 ​

6.2 快速排序：另一种分治 ​

七、设计反思：分治的失败案例 ​

7.1 失败案例1：最长递增子序列（LIS） ​

7.2 失败案例2：最短路径问题 ​

7.3 失败总结：分治的三禁忌 ​

八、知识卡片 ​

C12-01 分治三步法 ​

C12-02 递归树分析 ​

C12-03 分治正确性 ​

C12-04 分治 vs 贪心 ​

C12-05 分治 vs DP ​

C12-06 分治失败案例 ​

C12-07 并行分治 ​

C12-08 分治直觉建立 ​

九、练习设计 ​

基础练习（理解分治） ​

进阶练习（分治应用） ​

设计练习（分治 vs DP） ​

开放练习 ​

12.1 分治回顾：把大问题切成小块

一、问题情境：如何高效排序一个大数组？

二、直觉引入：切蛋糕的艺术

2.1 什么是分治？

2.2 分治三步法

2.3 为什么"独立"这么重要？

三、算法定义：分治形式化

3.1 分治的递推方程

3.2 主定理（Master Theorem）

四、实现示例：归并排序教学化代码

4.1 归并排序完整实现

4.2 代码背后的分治思想

五、复杂度分析：时间与空间

5.1 时间复杂度

5.2 空间复杂度

六、与前章节关联：分治在哪里出现过？

6.1 分治前章节应用

6.2 快速排序：另一种分治

七、设计反思：分治的失败案例

7.1 失败案例1：最长递增子序列（LIS）

7.2 失败案例2：最短路径问题

7.3 失败总结：分治的三禁忌

八、知识卡片

C12-01 分治三步法

C12-02 递归树分析

C12-03 分治正确性

C12-04 分治 vs 贪心

C12-05 分治 vs DP

C12-06 分治失败案例

C12-07 并行分治

C12-08 分治直觉建立

九、练习设计

基础练习（理解分治）

进阶练习（分治应用）

设计练习（分治 vs DP）

开放练习