分治算法

文章结构

1. 如何理解分治算法
2. 分治算法应用举例

1. 如何理解分治算法

1.1 分治算法的核心思想

分治算法的核心思想简单来说就四个字，分而治之。也就是将一个大的问题分解成多个规模较小但是结构相似的子问题，递归的解决这些子问题，然后合并这些子问题的解来得到原问题的解。

1.2 分治算法的递归实现思路

分治算法一般比较适合用递归来实现。分治算法的递归实现，每一层都涉及这样三个操作：

1. 分解：将原问题分解成一些列的子问题
2. 解决：递归的求解各个子问题，若子问题足够小，则直接求解
3. 合并：将子问题的解合并成原问题的解

1.3 什么样的问题适合用分治思想来解决

1. 一个问题能够分解成多个结构相似、规模较小的子问题
2. 子问题要能够独立求解，彼此之间没有相关性
3. 问题分解要有终止条件，也就是当问题足够小的时候，可以直接解决
4. 合并子问题的解的复杂度不能太高，否则就起不到减少算法总体复杂度的效果

2. 分治算法应用举例

2.1 归并排序

归并排序就是典型的分治思想应用。归并排序的思想就是：先将要排序的数据分成两个部分，先对这两个部分进行排序，然后再将排好序的两个有序序列进行合并。

2.2 海量数据排序

假设有10GB的订单文件需要按照金额进行排序，而能够使用的及其内存只有2、3个GB，如何进行排序呢？

可以先将这些数据分成多份，然后将每一份数据单独调入内存进行排序，待每份数据都排好序之后。在将这些数据合并成一个有序序列。