分治算法的核心思想

核心观点

分治算法把原问题拆成若干个规模更小的同类子问题，分别求解后再合并成原问题的解。

分治真正省下的不是代码量，而是每一层需要处理的规模：拆分、求解、合并三步的成本都必须低于直接求解原问题，这套结构才成立。子问题必须与原问题同构，否则无法递归；合并如果比求解本身还重，分治就只剩下形式。

知识连接

• 建立在：算法：递归的核心概念和应用要点——分治靠递归重复处理同构的子问题，递归是它的执行方式。
• 例证：归并排序的核心思想——拆分几乎无成本，代价落在合并上，是”拆分—求解—合并”三段最完整的形态。
• 例证：快速排序的核心思想——分区后基准已经就位，左右区间递归处理，不需要额外合并。
• 例证：算法：二分查找——只保留”不断缩小范围”这一半，没有合并阶段，是分治的退化形态。
• 导向：复杂度分析的核心概念和应用要点——判断分治是否值得用，要比较每层拆分、合并的成本与子问题的数量。