分治法

  “分治法”是计算机领域中最常见的算法类型，其核心思想是“分而治之”。其原理是将一个复杂问题拆分成两个或多个相同的子问题，然后将子问题依然进行分治法处理，直到子问题已经可以直接求解，最终按照问题的拆解顺序，将子问题开始逐步将问题合并成一个更大的子问题，逐层向上，最终得到原复杂问题的解。
  分治法通常可以解决的问题类型有如下几种：

1. 待求解问题是可以拆分为若干个相同或者相似的子问题，子问题直接相互独立。
2. 该问题可以在小规模情况下成立，并得到解。
3. 问题拆分后的结果可以进行合并。

  分治法解决问题的一般步骤如下：

1. 分解问题。将原问题拆解为若干相同或者相似、相互独立的子问题。
2. 解决子问题。如果拆分的子问题不能进行直接求解，则继续拆分子问题，知道可以直接进行求解为止。
3. 合并解。从可以直接解决的子问题入手，开始合并子问题的解，最终合并得到原始问题的解。

分治法的一般的算法设计模式如下：

    Divide-and-Conquer(P)
    1. if |P|≤n0
    2. then return(ADHOC(P))
    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
    4. for i←1 to k
    5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
    7. return(T)

  分治法经常采用递归的方式进行求解，因为递归可以有效地将问题拆解为相似且更小的子问题，且子问题直接相互独立。但是，如果子问题之间存在相同或重复子问题是，可能会影响分治法的计算效率，因为同样的问题在不同的子问题中会被重复计算。这种情况下，可以使用动态规划法保存中间结果的方法进行改善。
  常见的利用分治法思想的算法有：二分查找，归并排序，快速排序等。归并排序的过程示意如下：

image