分治算法解题套路框架
raw/articles/2026/05/分治算法解题套路框架
一句话总结
区分广义分治思想与狭义分治算法的核心差异，讲解分治算法通过问题分解降低时间复杂度的原理及递归解题框架。
核心要点
1. 分治思想 vs 分治算法
- 分治思想：宽泛的分解问题思路，将问题拆解为子问题求解后合并，广泛应用于递归算法（如斐波那契递归、二叉树节点计数、动态规划等）
- 分治算法：特指分解后求解比直接求解复杂度更低的递归算法，需满足分解带来的效率提升（如桶排序、归并排序）
2. 复杂度降低原理
- 数学类比：$(a+b)^2 = a^2 + 2ab + b^2 \geq a^2 + b^2$
- 原问题规模 $N=a+b$，直接求解 $O(N^2)$ 复杂度为 $O((a+b)^2)$
- 分解为子问题后分别求解，复杂度为 $O(a^2 + b^2) < O((a+b)^2)$
- 适用条件：仅多项式级别复杂度的算法可能通过分治提升效率
3. 解题框架
分治算法本质是分解问题的递归思路，类似二叉树后序遍历：
- 分解原问题为结构相同的子问题
- 递归求解子问题
- 合并子问题的解得到原问题解
基本原理
| 概念 | 说明 |
|---|---|
| 分治思想 | 所有递归算法的两种思路之一（另一种是遍历思路），用于分解问题 |
| 分治算法 | 分治思想的特例，要求分解后求解效率高于直接求解 |
| 多项式复杂度 | 分治算法仅对 $O(N^k)$ 类算法可能提升效率 |
相关概念
- 分治算法：分解独立子问题，递归求解后合并（归并/快排）
- 递归：从树的角度理解递归，两种思维模式：遍历 vs 分解问题
- 动态规划：分解问题+记忆化，避免重复计算的递归优化
- 回溯算法：遍历思维+状态管理，做选择→递归→撤销选择
- 后序遍历：能获取左右子树信息，归并排序=后序遍历的应用
- 归并排序：分治排序，O(n log n)稳定排序，结合二叉树后序遍历理解
- 桶排序：分桶后分别排序的非比较排序，分治思想提升效率的典型案例
相关实体
- labuladong：算法学习平台 labuladong.online 作者，本文来源
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 23. 合并 K 个升序链表 | 困难 |
| LeetCode | 23. Merge k Sorted Lists | Hard |
总结
分治思想是所有递归算法的基础思维模式之一，而分治算法是其中能通过问题分解降低时间复杂度的特殊子集，核心判断标准是「分解后求解是否比直接求解更高效」。
待补充
由于原文包含更多实战例题（如合并K个升序链表的具体实现），当前仅获取了核心原理部分，后续可补充完整解题示例。