算法——分治算法(1)

本文最后更新于:1 年前

本文章只介绍理论,下一篇讲解实例!!

(一)概念:

分治法,即"分而治之",意即将一个复杂的问题分解成若干个相同或者相似的子问题,再将这些子问题继续进行分解,直到产生足够简单能够直接求解的子问题。而对原问题的求解,就是对这些子问题的合并。

分治算法可以由递归过程来表示,因为分治法是大规模问题化为小规模问题的方法,是递归设计的一种具体策略。

因为计算机求解的计算时间往往与其规模有关,通过分治法来减少问题求解的规模,进而减少计算时间,对于大规模运算来说,是很重要的。

分治算法是很多高效算法的基础,如二分查找,归并和快速排序,大整数乘法,矩阵乘法,傅里叶变换等等。

(二)基本思想和特征:

分治策略:对于一个规模为n的问题,若可直接解决则直接解决,否则将其分解为k个规模较小的子问题,子问题之间要互相独立且与原问题形式相同,递归解决子问题后,可以将其合并得到原问题的解。

对这k个子问题,1<k<=n,且每个子问题是可以利用其子问题的解求出自身的解,进而求出原问题的解的。

互相独立是指子问题之间不能独自占用其公共的资源,产生问题间的冲突,也就是互不相交,互不影响。

形式相同是指其具有最优子结构,也就是大问题的最优解是由小问题的最优解组成的,不会出现非最优解的小问题合并出了最优解的大问题。

分治法的使用特征一般为:

  1. 问题的规模缩小到一定的程度其最优解或唯一解是显然的。对于大多数问题,此特征是成立的。(问题复杂性一般随着问题规模增加)

  2. 问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。此特征是应用分治法的前提,大部分问题也可以满足此条件。(体现了递归思想)

  3. 利用该问题分解出的子问题的解可以合并为该问题的解。这是应用分治法的关键,能否利用分治法完全取决于是否具备此特征(如果具备前两个特征而不具备此特征,一般从动态规划和贪心算法的角度考虑)

  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。此特征是分治法解决问题效率的关键,一般情况下,如果有重复的公共子问题,使用动态规划算法更好。

基本步骤:

整体上,分治法是由不断的递归实现的。

对于每一层的递归分治法都有以下三个步骤:

  • 分解:将原问题分解为k个规模较小,相互独立,与原问题形式相同的子问题。

  • 解决:若子问题规模较小而容易被解决则直接解决,否则递归地解各个子问题。

  • 合并:将各个子问题的解合并为原问题的解。

分治法的复杂性分析:

分治法将规模为n的问题分成a个规模为n/b的子问题去求解,直到n达到分解阈值以下时才可以直接求解。

设分解阈值n0=1,解规模为1的问题花费常数时间,分解k个子问题和合并k个子问题需要F(n)的时间,通常情况下,此时间我们认为就是 O(nd)的时间。则有:

这就是分治算法的时间复杂度公式。

分治算法的主定理求解时间求解复杂度:

此处不给出主定理的证明,而是直接说明结论:

对于a,b,d均大于0时,有:

屏幕截图 2023-03-29 185948

使用时,确定a,b和d值即可确定分治法的时间复杂度了。

分治法与动态规划的区别:

动态规划除了分治法的要求外,还要求存在重叠子问题。

此处要解释一下,子问题相互独立和重叠子问题并不是矛盾的,它们是两个不同的概念,不是一个问题的不同方面。

前者说明了子问题是不共享资源的,或者说,它们之间不会存在互相抢占资源,争夺资源的问题。

而后者说明的是同一个子问题在不同的问题中出现了,也就是在两个不同的问题中分解后能够得到一个相同的子问题,这个子问题就是重叠子问题。

自顶向下的动态规划可以看作是带备忘的分治法。


算法——分治算法(1)
https://github.com/xiaohei07/xiaohei07.github.io/2023/03/21/算法——分治算法(1)/
作者
07xiaohei
发布于
2023年3月21日
许可协议