分治算法

2019/08/16 算法

分治算法

思想——分而治之

将原问题划分成 n 个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。

适用场景

  • 原问题与分解成的小问题具有相同的模式;
  • 原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别;
  • 具有分解终止条件,也就是说,当问题足够小时,可以直接求解;
  • 可以将子问题合并成原问题,而这个合并操作的复杂度不能太高,否则就起不到减小算法总体复杂度的效果了。

方式

  • 分解:将原问题分解成一系列子问题;
  • 解决:递归地求解各个子问题,若子问题足够小,则直接求解;
  • 合并:将子问题的结果合并成原问题。

结果

用贪心算法解决问题的思路,并不总能给出最优解。(有权图,从一个顶点到另一个顶点的最短路径,贪心算法不工作的主要原因是,前面的选择,会影响后面的选择。如果我们第一步从顶点 S 走到顶点 A,那接下来面对的顶点和边,跟第一步从顶点 S 走到顶点 B,是完全不同的。所以,即便我们第一步选择最优的走法(边最短),但有可能因为这一步选择,导致后面每一步的选择都很糟糕,最终也就无缘全局最优解了。)

经典应用

归并排序

范例

  1. 二维平面上有 n 个点,如何快速计算出两个距离最近的点对?
  2. 有两个 n*n 的矩阵 A,B,如何快速求解两个矩阵的乘积 C=A*B?
  3. 还经常用在海量数据处理的场景中(比如,给 10GB 的订单文件按照金额排序这样一个需求,看似是一个简单的排序问题,但是因为数据量大,有 10GB,而我们的机器的内存可能只有 2、3GB 这样子,无法一次性加载到内存,也就无法通过单纯地使用快排、归并等基础算法来解决了。有一个点要注意,就是数据的存储与计算所在的机器是同一个或者在网络中靠的很近(比如一个局域网内,数据存取速度很快),否则就会因为数据访问的速度,导致整个处理过程不但不会变快,反而有可能变慢)
  4. 如何编程求出一组数据的有序对个数或者逆序对个数呢?

Search

    Table of Contents