分治算法的基本知识记录

分治算法的全称应该是分而治之（ divide and conquer， D&C）

一、概念

1、简单定义

分治算法的核心思想是将原问题划分成规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

2、性质

D&C并非可用于解决问题的算法，而是一种解决问题的思路。

3、基本要求

根据D&C的定义，每次递归调用都必须缩小问题的规模。

二、步骤

使用D&C解决问题的过程最重要的是两个步骤。
(1) 找出基线条件，这种条件必须尽可能简单。
(2) 不断将问题分解（或者说缩小规模），直到符合基线条件。

最后将问题递归解决，并合并出最终的解

三、核心思路

与核心思路相对应的，分治思想核心思路也是两条
1、 找出简单的基线条件；
2、 确定如何缩小问题的规模，使其符合基线条件。

基线条件的定义参见递归算法的相关概念

四、使用条件

使用D&C解决问题，往往需要满足以下条件，才能实现或充分发挥D&C的优越性

1、问题的规模缩小到一定的程度 可以直接求解

2、问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质

3、利用分解出的子问题的解 可以合并为问题的解

4、分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题