何为分治？简单来说，就是将大的问题分解成小问题进行求解，然后对每个小问题的解进行处理【一般是合并】为大问题的解，下面是分治较为官方的说明：

分治： 把一个任务，分成形式和原任务相同，但规模更小的 几个部分任务（通常是两个部分），分别完成，或只需要选一部完成。然后再处理完成后的这一个或几个 部分的结果，实现整个任务的完成。

斐波那契数列

我想了很多，最后发现还是从这个例子开始说起更加便于理解。

斐波那契数列的定义很简单，其最早的历史来自于那个生兔子的问题。斐波那契数列的解法众多，详细描述可见维基百科，而如果使用数学公式来描述，那么就是这个样子的： \[ \begin{equation} \left\{ \begin{array}{**lr**} F_0 = 0 & \\ F_1 = 1 & \\ F_n = F_{n-1} + F_{n-2} & \\ \end{array} \right. \end{equation} \] 他这种递归的定义方式，其实以初等数学使用暴力求解的思路来说，刚好是符合我们的分治思想的。因为你若将求解 \(F_4\) 看作一个大问题，就必须将其分解为两个小一点的子问题，即求解 \(F_3\) 和 \(F_2\) ，然后再计算二者之和。

那么根据这个递归式，我想只要有点语言基础，都能很快写出一段递归的代码进行求解：

1
2
3
4
5
6
7
8
int Fibonacci(int n) {
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;

	return Fibonacci(n-1) + Fibonacci(n-2);
}

当然，Fibonacci 真正实现的时候不能这么写。

分治范式

大致对分治这种思想有了一个整体认识之后，我们便可以总结出一个求解分治问题的范式：

何时使用分治思想：问题规模太大或者其他原因导致难以直接求解，那么这时候便可以考虑将问题划分为子问题，通过求解子问题来实现原问题最终的求解。

范式的一般步骤：

  • 划分：简单来说，此步骤就是将大问题分解为小问题【注：每个小问题的求解必须一致，不然分治就失去了其原本的意义】。
  • 治理：1也就是对每一个子问题进行求解。
  • 组合：将所有子问题的结果进行合并，得到原问题的解。

分治的分析

分治的性质决定了其与递归联系紧密，所以如果一个问题可以用分治的思想来解决，那么其必然可以转化为一个递归表达式，就如同最开始直接以递归定义的斐波那契数列的表达式一般。而此类问题时间复杂度的详细分析，也往往依靠求解这样的递归式来得到。

归并排序

许多算法都是利用分治思想提出来的，而归并排序无疑是最具代表性的一个，我们可以根据分治范式来一步步分析求解，最终明确这个算法的原理。

划分

  • 两个数之间如何排序【注：此后所说的排序均代表顺序排序】？很显然两两之间比较，小的放左边，大的放右边。
  • 那三个数如何排序？选两个排好之后，再将第三个数与已经排好的两数比较，进而确定第三个数的位置。
  • 四个？此时可以两两排好，然后再合并两个已排序的数组即可。
  • 六十四个？可以分为俩三十二个的，每个三十二个的又可分为俩十六个的……

如此，我们可以将大问题以对半划分的方式【注：奇数对半，一半比一半多1即可】层层划分，直至不可划分为止，也就是仅剩一个数的时候。而划分，也往往就是递归的过程。

治理

治理，即解决划分后的子问题，划分后的子问题是什么呢？答案就是，一个数的排序。一个数显然无需排序，那么此步骤便无需进行处理。

组合

将子问题的结果组合起来，在此问题中便是，将已排序的两个数组合并为一个已排序的数组。

具体实现

分析清楚之后便可自己尝试写出代码了，首先要写的，便是 组合 部分，C语言代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
	- 将数组a的局部a[l,r-1]和a[r,rightEnd]合并到tmp
    - 然后再拷贝回a[l,rightEnd]
**/
void merge(int a[], int l, int r, int rightEnd, int tmp[]) {
	int leftEnd = r - 1; 
	int left = l, count = l;

	while (l <= leftEnd && r <= rightEnd) {
		if (a[l] < a[r])
			tmp[count++] = a[l++];
		else 
			tmp[count++] = a[r++];
	}

	while (l <= leftEnd)
		tmp[count++] = a[l++];
	while (r <= rightEnd)
		tmp[count++] = a[r++];

	for (int i = left; i < rightEnd+1; i++) 
		a[i] = tmp[i];
}

然后，就可以完成划分部分，从而进行排序了。C语言代码如下：

1
2
3
4
5
6
7
8
void mergeSort(int a[], int left, int rightEnd, int tmp[]) {
	if (left < rightEnd) {
		int mid = left + (rightEnd-left)/2;
		mergeSort(a, left, mid, tmp);	// 划分左半部分
		mergeSort(a, mid+1, rightEnd, tmp);	// 划分右半部分
		merge(a, left, mid+1, rightEnd, tmp);	// 组合子问题的解
	}
}

汉诺塔问题

作为练习，可尝试自己实现一下汉诺塔问题！【待补】

  1. 此处按照教科书上（算法技巧与分析【沙特】）来说，此步骤实质上是一种优化复杂度的步骤，但在此，为了简便起见，直接将其写为了子问题的求解。↩