分治法

分治法的基本思想在上回的递归中已经讲的差不多了。 就是将规模较大的问题分解成规模较小的问题。

T(n) = aT(n/b) + f(n) (a>=1; b>1)

T(n) 就是规模为n的问题， 可以分解成a个规模为n/b的同类型的问题， 再加上分解过程的开销(汉诺塔的move, 布尔组合的set value)。

虽说对无序的序列采取分治没什么意义， 但这里仅仅只是用来说明分治的思想， 故例与此。

例： 从数组中找出最大、最小值
【方法一】

int min = a[0], max = a[0];
for(int i = 1; i < a.length; i++) {
    if(a[i] < min) min = a[i];
    if(a[i] > max) max = a[i];
}

一共 2×n-2 次比较。

【方法二】

public class FindMinMax {

	private static int MIN;
	private static int MAX;

	public static void main(String[] args) {
		int[] a = new int[] { 6, -111112, 1, 7, 4, 8, 2, 0, 100, 12, -100, -1, -43, 1912, 11, 77, -9999 };
		MIN = MAX = a[0];
		int[] res = find(a, 1, a.length - 1);
		System.out.println("Min: " + res[0]);
		System.out.println("Max: " + res[1]);
	}

	private static int[] find(int[] a, int from, int to) {
		if (from + 1 == to || from == to) {
			if (a[from] < a[to]) {
				MIN = MIN < a[from] ? MIN : a[from];
				MAX = MAX > a[to] ? MAX : a[to];
			} else {
				MIN = MIN < a[to] ? MIN : a[to];
				MAX = MAX > a[from] ? MAX : a[from];
			}
		} else {
			int mid = (from + to) / 2;
			find(a, from, mid);
			find(a, mid + 1, to);
		}

		return new int[] { MIN, MAX };
	}
}

一共3n/2-2次比较。

所以从效率上还是比遍历稍好些。

对于分治法的其他些算法如： 二分查找， 快排， 归并， 插入等以后再补充。

-------------------------- 我是分割线 ----------------------------