分治Divide and conquer
把问题分成较小子问题，分别求解并组合结果。
- 核心约束
- 子问题与合并步骤共同保留原问题语义。
- 适用问题
- 归并排序、分块计算与递归分解。
- 边界与取舍
- 不能仅凭递归形式推断复杂度，需分析递推关系。
时间与空间#
a 为子问题数量，n/b 为子问题规模，f(n) 为分割与合并工作。
- 时间成本
- 由递推式 T(n) = a T(n/b) + f(n) 决定
- 空间成本
- 由递归深度、子问题是否并行和临时数组决定
例如归并排序 a=2、b=2、f(n)=，得到 。主定理有适用条件，不能处理所有不均匀分割；递归树可用于核算各层工作。
工程中的应用#
1 个案例 · 附源码FFmpeg 的 AAC 编码器通过 av_tx_init 取得 MDCT 函数。通用实现用折叠、旋转与半长 FFT 完成变换，FFT 再分解为较小子变换。
附源码片段 · 音视频处理
基础原理参考资料
MIT 6.006 · Sorting通过归并排序分析分治递推与合并成本。