14.3.3 分治法

分治法的思想是“分而治之”：把大问题划分为若干规模较小、结构相同且相互独立的子问题，分别求解后再合并结果。

三步结构

1. 分解：把原问题分成若干子问题。
2. 求解：递归求解子问题，直到足够小。
3. 合并：把子问题结果合成原问题结果。

flowchart TD
  A["原问题"] --> B["子问题1"]
  A --> C["子问题2"]
  A --> D["子问题..."]
  B --> E["子结果1"]
  C --> F["子结果2"]
  D --> G["子结果..."]
  E --> H["合并为原问题解"]
  F --> H
  G --> H

常见例子

算法	分治体现
二分查找	每次舍弃一半搜索区间
归并排序	二分数组，分别排序，再归并
快速排序	选枢轴划分左右区间，再递归排序

分治与递归

分治常用递归实现，但递归不等于分治。斐波那契朴素递归也是“自己调用自己”，但它的子问题大量重叠，不是软考中典型的二分分治考点。

本节例题

单选

分治法的一般步骤是：

A分解、求解、合并B入队、出队、回退C散列、冲突、装填D尝试、失败、撤销

自查清单

1. 能否说明分治的子问题通常应相互独立？
2. 能否区分“递归”与“分治”？
3. 能否把二分查找、归并排序和快速排序归入分治思想？