JavaChen Blog

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技 术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递 归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加 而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具 有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多 问题可以取 k = 2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

二分法查找是典型的分治法的例子，下例是java中的二分查找法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class BinarySearch {
 
	public BinarySearch() {
	}
 
	public static int binarySearch(int[] datas, int key) {
		int index = -1;
		int low = 0;
		int high = datas.length - 1;
		while (low < = high) {
			int middle = (low + high) >> 1;
			if (key == datas[middle]) {
				index = middle;
				break;
			} else if (key > datas[middle]) {
				low = middle + 1;
			} else if (key < datas[middle]) {
				high = middle - 1;
			}
		}
		return index;
	}
 
	public static void main(String[] args) {
		int[] datas = { 1, 2, 3, 4, 5, 6 };
		int index = BinarySearch.binarySearch(datas, 6);
		System.out.println(index);
	}
}

容易看出，每执行一次算法的while循环，待搜索数组的大小就减小一半。因此，最坏情况下，while循环被执行了O（log n）次。循环体内，运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（log n）。

利用分治法的思想还可以解决大整数乘法的问题

通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。
设计如下：
设X和Y都是n位的二进制整数，现在要计算它们的乘积X*Y。
将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)。显然问题的答案并不是 A*C*K1+C*D*K2（K1、K2与A、B、C、D无关），也就是说，这样做并没有将问题分解成两个独立的子问题。按照乘法分配律，分解后的计算过程如下：
记：X=A*2n/2+B ，Y=C*2n/2+D。这样，X和Y的乘积为：
X*Y=(A*2n/2+B)(C*2n/2+D)=A*C*2n+(AD+CB)*2n/2+B*D (1)
模型分析：
如果按式(1)计算X*Y，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法，此外还要做2次移位 (分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有以下(2)式：
T（1）=1
T（n）=4T(n/2)+O(n) （2）
由此递归式迭代过程如下：
T(n)=4T(n/2)+cn =4(4T(n/4)+cn/2)+cn
=16(T(n/8)+ cn/4)+3cn/2+cn =……
= +4k-1 *2c+4k-2 *4c+……+4c2k-1+c2k
=O（4k）= O(nlog4)
=O（n2）
所以可得算法的时间复杂度为T(n)=O(n2)。
模型改进：
可以把X*Y写成另一种形式：
X*Y=A*C*2^n+[(A-B)(D-C)+AC+BD]*2^(n/2)+B*D (3)
式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法：AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得:
用解递归方程的迭代公式法，不妨设n=2^k：
T(n)=3T(n/2)+cn
=3(3T(n/4)+cn/2)+cn
=9(T(n/8)+ cn/4)+3cn/2+cn
=……
=3^k +3^(k-1) *2c+3^(k-2) *4c+……+3c2^(k-1)+c2^k
= O(n^log3)
则得到T(n)=O(n^log3)=O(n^1.59)。