算法——分治算法(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(n^d)的时间。则有：

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

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

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

对于a，b，d均大于0时，有：

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

¶分治法与动态规划的区别：

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

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

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

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

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