一, 分治算法概述

1.1 分治法的思想和特点

分治算法是采用了分治思想的一种算法, 什么是分治呢?

分值策略: 分治, 字面上的解释就是"分而治之",将原问题划分为n个规模较小而结构与原问题相似的子问题; 递归的解决这些子问题, 然后再合并其结果, 就得到原问题的解;

将父问题分解为子问题的同等方式求解, 这和递归的概念很吻合, 所以在分治算法通常以递归的方式实现(当然也是有非递归的实现方式). 分治算法的描述从字面上也很容易理解, 分, 治, 其实还有个合并的过程:
- 分解(Divide): 将原问题分解为一系列子问题
- 治(解决)(Conquer): 递归地解各子问题, 若子问题足够小, 则直接求解;
- 合并(Combine): 将子问题的结果合并为原问题的解;

一般分治算法在正文中分解为两个及以上的递归调用, 并且子问题一般是不相交的(互不影响).
当求解一个问题规模很大很难直接求解, 但是在规模较小的时候问题很容易求解并且这个问题满足分治算法的适用条件, 那么就可以适用分值算法;

1.2 分治法的适用条件:

这里不得不提到分治算法的适用条件:
分治法能解决的问题一般具有以下几个特征:

1. 该问题的规模缩小到一定的程度就可以很容易的解决;
2. 该问题可以分解为若干个规模较小的相同问题, 即该问题具有最优子结构性质;
3. 利用该问题分解出的子问题的解可以合并为该问题的解;
4. 该问题分解出的各个子问题是相互独立的, 即子问题之间不包含公共的子子问题;

上述的第一条特征(问题规模缩小能解决问题)是绝大多数问题都可以满足的, 因为问题的计算复杂性一般是随着问题规模的增加而增加;
–第二条特征(问题可以分解为规模较小的相同问题)是应用分治法的前提, 它也是大多数问题可以满足的, 此特征反映了递归思想的应用;
–第三条特征(子问题的解能够合并出原问题的解)是关键, 能否利用分治法完全取决于问题是否具有第三条特征, 如何具备了第一特征和第二特征, 而不具备第三特征, 则考虑用贪心法或动态规划法.
– 第四条(子问题相互独立)特征涉及到分治法的效率, 如果各子问题是不独立的, 则分治法要做许多不必要的工作,重复的解公共的子问题, 此时虽然可用分治法, 但是最适合的还是用动态规划.

1.3 应用分治算法的基本步骤

分治算法在每一层递归上都有三个步骤:

step 1. 分解: 将原问题分解为若干个规模较小, 相互独立, 与原问题形式相同的子问题;

step 2. 解决: 若子问题规模较小而容易被解决则直接解决, 否则递归的解各个子问题;

step 3. 合并: 将各个子问题的解合并为原问题的解;

二, 分治算法的经典问题

对于分治算法的经典问题, 重要的是学会其思想, 因为大部分情况下我们都是借助于递归去实现, 所以代码比较简单;

分值算法的经典问题, 大致有两类:
子问题完全独立 和 子问题不完全独立

1. 子问题完全独立就是原问题的答案可完全由子问题的结果推出;
2. 子问题不完全独立, 有些区间类的问题或跨区间问题使用分治可能结果跨区间(比如 利用分治法求最大子序列和时), 我们在使用分治的时候要注意区分;

2.1 二分查找

二分查找是分治的一个实例, 只不过二分搜索有着自己的特殊性
- 待搜索序列必须是有序的;
- 搜索结果是一个值

正常的分治法中的分解是不断向下细分区间, 并对每一个区间都要进行求解, 然后二分查找是不断的细分有序区间和确认正确的区间范围, 并丢弃不符合条件的区间.

[具体实现]
Java实现二分查找

2.2 快速排序

快排也是分治的一个实例，快排每一趟会选定一个数，将比这个数小的放左面子区间，比这个数大的放右面子区间，然后继续往下递归分治求解两个子区间，当然快排因为在分的时候就做了很多工作，当全部分到最底层的时候这个序列的值就是排序完的值。这是一种分而治之的体现。

原理图:

[具体实现]
Java实现快速排序

2.3 归并排序

快排在分的时候做了很多工作，而归并就是相反，归并在分的时候按照数量均匀分，而合并时候已经是两两有序的进行合并的，因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

原理图:

[具体实现]

Java实现归并排序

2.4 最大子序列和

具体实现:

LeetCode 53. 分治法解决最大子序列和(Java)

参考资料:

分治算法