分治算法
在算法设计中，常常引入分而治之的策略，称之为分治算法，其本质就是将一个大规模的问题分解为若干规模较小的相同子问题，分而治之1。分治算法是一种解题的思想，并不是某种如冒泡排序算法一样的固定的算法。
分治算法要点
一个问题是否可以用分治算法来解决，可以通过下面 3 个条件来判断。
- 原问题可以被分解为若干个规模较小的子问题，这些子问题是原问题的一个子集；
- 子问题之间相互独立；
- 子问题的解可以合并为原问题的解。
在分治策略中，当我们递归求解一个问题是，在每层递归时都有三个步骤2。
- 分解：原问题分为若干个子问题，子问题的形式与原问题一样，只是规模更小。
- 解决：递归求解出子问题。如果子问题规模足够小，则停止递归，直接求解。这里隐含的意思是，子问题在求解时还可以分成更小的子问题。
- 合并：将子问题的解组合成原问题的解。
递归
递归（英语：Recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法3。
- 递归
- 在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况3。
在计算机科学中，递归是一种程序结构。递归不仅仅应用在分治算法中，在其他算法中也有很广的应用，如树和图的遍历等。
以下是一个用以计算阶乘的方法，此方法中即使用了递归的思想。
function fact(n: Number): Number {
if (n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
Note
这里使用的是 Typescript 语言编写的函数，在 Java 中也是类似的。
哪些算法使用了分治法
以下列举出一些使用了分治法的具体算法，可以从这些算法中体会分治思想的妙用。
- 归并排序（Merge Sort）
- 最大子数组问题（Maximum Subarray Problem）
- 快速排序（Quick Sort）
- 二分查找（Binary Search）
- Strassen 矩阵乘法
- 大整数乘法（Karatsuba Algorithm）
后续更新完对应算法，再补充连接