分治算法知识 #
1. 分治算法简介 #
1.1 分治算法的定义 #
分治算法(Divide and Conquer):字面上的解释是「分而治之」,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
简单来说,分治算法的基本思想就是: 把规模大的问题不断分解为子问题,使得问题规模减小到可以直接求解为止。
1.2 分治算法和递归算法的异同 #
从定义上来看,分治算法的思想和递归算法的思想是一样的,都是把规模大的问题不断分解为子问题。
其实,分治算法和递归算法的关系是包含与被包含的关系,可以看做:递归算法 ∈ 分治算法
。
分治算法从实现方式上来划分,可以分为两种:「递归算法」和「迭代算法」。
分治算法一般都比较适合使用递归算法来实现。但除了递归算法之外,分治算法还可以通过迭代算法来实现。比较常见的例子有:快速傅里叶变换算法、二分查找算法、非递归实现的归并排序算法等等。
1.3 分治算法的适用条件 #
分治算法能够解决的问题,一般需要满足以下 $4$ 个条件:
- 原问题可以分解为若干个规模较小的相同子问题。
- 分解出来的子问题可以独立求解,即子问题之间不包含公共的子子问题。
- 具有分解的终止条件,也就是说当问题的规模足够小时,能够用较简单的方法解决。
- 子问题的解可以合并为原问题的解,并且合并操作的复杂度不能太高,否则就无法起到减少算法总体复杂度的效果了。
2. 分治算法的基本步骤 #
使用分治算法解决问题主要分为 $3$ 个步骤:
- 分解:把要解决的问题分解为成若干个规模较小、相对独立、与原问题形式相同的子问题。
- 求解:递归求解各个子问题。
- 合并:按照原问题的要求,将子问题的解逐层合并构成原问题的解。
其中第 $1$ 步中将问题分解为若干个子问题时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的 $k$ 个子问题的处理方法是行之有效的。在许多问题中,可以取 $k = 2$。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。
其中第 $2$ 步的「递归求解各个子问题」指的是按照同样的分治策略进行求解,即通过将这些子问题分解为更小的子子问题来进行求解。就这样一直分解下去,直到分解出来的子问题简单到只用常数操作时间即可解决为止。
在完成第 $2$ 步之后,最小子问题的解可用常数时间求得。然后我们再按照递归算法中回归过程的顺序,由底至上地将子问题的解合并起来,逐级上推就构成了原问题的解。
按照分而治之的策略,在编写分治算法的代码时,也是按照上面的 $3$ 个步骤来编写的,其对应的伪代码如下:
|
|
3. 分治算法的复杂度分析 #
分治算法中,在不断递归后,最后的子问题将变得极为简单,可在常数操作时间内予以解决,其带来的时间复杂度在整个分治算法中的比重微乎其微,可以忽略不计。所以,分治算法的时间复杂度实际上是由「分解」和「合并」两个部分构成的。
一般来讲,分治算法将一个问题划分为 $a$ 个形式相同的子问题,每个子问题的规模为 $n/b$,则总的时间复杂度的递归表达式可以表示为:
$T(n) = \begin{cases} \begin{array} \ \Theta{(1)} & n = 1 \cr a * T(n/b) + f(n) & n > 1 \end{array} \end{cases}$
其中,每次分解时产生的子问题个数是 $a$ ,每个子问题的规模是原问题规模的 $1 / b$,分解和合并 $a$ 个子问题的时间复杂度是 $f(n)$。
这样,求解一个分治算法的时间复杂度,就是求解上述递归表达式。关于递归表达式的求解有多种方法,这里我们介绍一下比较常用的「递推求解法」和「递归树法」。
3.1 递推求解法 #
根据问题的递归表达式,通过一步步递推分解推导,从而得到最终结果。
以「归并排序算法」为例,接下来我们通过递推求解法计算一下归并排序算法的时间复杂度。
我们得出归并排序算法的递归表达式如下:
$T(n) = \begin{cases} \begin{array} \ O{(1)} & n = 1 \cr 2T(n/2) + O(n) & n > 1 \end{array} \end{cases}$
根据归并排序的递归表达式,当 $n > 1$ 时,可以递推求解:
$\begin{align} T(n) & = 2T(n/2) + O(n) \cr & = 2(2T(n / 4) + O(n/2)) + O(n) \cr & = 4T(n/4) + 2O(n) \cr & = 8T(n/8) + 3O(n) \cr & = …… \cr & = 2^x \times T(n/2^x) + x \times O(n) \end{align}$
递推最终规模为 $1$,令 $n = 2^x$,则 $x = \log_2n$,则:
$\begin{align} T(n) & = n \times T(1) + \log_2n \times O(n) \cr & = n + \log_2n \times O(n) \cr & = O(n \times \log_2n) \end{align}$
则归并排序的时间复杂度为 $O(n \times \log_2n)$。
3.2 递归树法 #
递归树求解方式其实和递推求解一样,只不过递归树能够更清楚直观的显示出来,更能够形象地表达每层分解的节点和每层产生的时间成本。
使用递归树法计算时间复杂度的公式为:
$时间复杂度 = 叶子数 * T(1) + 成本和 = 2^x \times T(1) + x \times O(n)$。
我们还是以「归并排序算法」为例,通过递归树法计算一下归并排序算法的时间复杂度。
归并排序算法的递归表达式如下:
$T(n) = \begin{cases} \begin{array} \ O{(1)} & n = 1 \cr 2T(n/2) + O(n) & n > 1 \end{array} \end{cases}$
其对应的递归树如下图所示。
因为 $n = 2^x$,则 $x = \log_2n$,则归并排序算法的时间复杂度为:$2^x \times T(1) + x \times O(n) = n + \log_2n \times O(n) = O(n \times log_2n)$。
4. 分治算法的应用 #
4.1 归并排序 #
4.1.1 题目链接 #
4.1.2 题目大意 #
描述:给定一个整数数组 nums
。
要求:对该数组升序排列。
说明:
- $1 \le nums.length \le 5 * 10^4$。
- $-5 * 10^4 \le nums[i] \le 5 * 10^4$。
示例:
|
|
4.1.3 解题思路 #
我们使用归并排序算法来解决这道题。
- 分解:将待排序序列中的 $n$ 个元素分解为左右两个各包含 $\frac{n}{2}$ 个元素的子序列。
- 求解:递归将子序列进行分解和排序,直到所有子序列长度为 $1$。
- 合并:把当前序列组中有序子序列逐层向上,进行两两合并。
使用归并排序算法对数组排序的过程如下图所示。
4.1.4 代码 #
|
|
4.2 二分查找 #
4.2.1 题目链接 #
4.2.2 题目大意 #
描述:给定一个含有 $n$ 个元素有序的(升序)整型数组 nums
和一个目标值 target
。
要求:返回 target
在数组 nums
中的位置,如果找不到,则返回 $-1$。
说明:
- 假设
nums
中的所有元素是不重复的。 - $n$ 将在 $[1, 10000]$ 之间。
- $-9999 \le nums[i] \le 9999$。
示例:
|
|
4.2.3 解题思路 #
我们使用分治算法来解决这道题。与其他分治题目不一样的地方是二分查找不用进行合并过程,最小子问题的解就是原问题的解。
- 分解:将数组的 $n$ 个元素分解为左右两个各包含 $\frac{n}{2}$ 个元素的子序列。
- 求解:取中间元素
nums[mid]
与target
相比。- 如果相等,则找到该元素;
- 如果
nums[mid] < target
,则递归在左子序列中进行二分查找。 - 如果
nums[mid] > target
,则递归在右子序列中进行二分查找。
二分查找的的分治算法过程如下图所示。
4.2.4 代码 #
二分查找问题的非递归实现的分治算法代码如下:
|
|
参考资料 #
- 【书籍】趣学算法 - 陈小玉 著
- 【书籍】算法之道 - 邹恒铭 著
- 【书籍】算法图解 - 袁国忠 译
- 【书籍】算法训练营 陈小玉 著
- 【博文】 从合并排序算法看“分治法” - 船长&CAP - 博客园
- 【博文】 递归、迭代、分治、回溯、动态规划、贪心算法 - 力扣
- 【博文】 递归 & 分治 - OI Wiki
- 【博文】 漫画:5分钟弄懂分治算法!它和递归算法的关系!