1。分治策略

分治策略分为三个部分【分解（Divide）、解决（Conquer）、合并（Combine）】

利用主方法求解递归式的界：

​
$$
T(n)=aT(n/b)+f(n)
$$
其中a≥1，b＞1，f(n)是一个给定的函数。一个分治算法：生成a个子问题，每个子问题的规模是原问题规模的1/b，分解和合并步骤总共花费时间为f(n)。

1.1最大子数组问题

要求：确定具有最大和的连续子数组

​ 利用分治的思想，每次寻找子数组A[low..high]的最大子数组时，无在乎分为三种情况

①.完全组在mid左侧;

②.完全组在mid右侧;

③.完全组穿过mid;

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
30
31
32
33
34
35
36
FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high){
	int left_sum=-1000000;
	int sum=0;
	int max_left=0;												//用来存储左界
	int max_right=0;										    //用来存储右界
	for(int i =mid;i>=low;i--){
		sum=sum+A[i];
		if(sum>left_sum){
			left_sum=sum;
			max_left=i;		
		}														//不断比较实现最大连续子树				
	}															//用来寻找左界
	int right_sum=-1000000;
	sum=0;
	for(int i =mid;i<=high;i++){
		sum=sum+A[i];
		if(sum>right_sum){
			right_sum=sum;
			max_right=i;
		}
	}
	return (max_left,max_right,left_sum+rght_sum);
}//O(1)的线性寻找，子数组的寻找。
FIND_MAXIMUM_SUBARRAY(A,low,high){
	if(high==low){
		return(low,high,A[low]);
	}else {
		mid=(low+high)/2;
		(left_low,left_high,left_sum)=FIND_MAXIMUM_SUBARRAY(A,low,mid);
		(right_low,right_high,right_sum)=FIND_MAXIMUM_SUBARRAY(A,mid+1,high);
		(cross_low,cross_high,cross_sum)=FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high);
		if(left_sum>=right_sum&&left_sum>=cross_sum) return (left_low,left_high,left_sum);//完全组在mid左侧
		else if(right_sum>=left_sum&&right_sum>=cross_sum) return(right_low,right_high,right_sum)//完全组在mid右侧
		else return (cross_low,cross_high,cross_sum);//完全组穿过了mid 最大值为left_sum+right_sum;
	}
}

1.2矩阵乘数的Strassen算法

A、B、C都分为分块矩阵 A11、A12、A21、A22、B11、B12、B21、B22、C11、C12、C21、C22

C11=A11 * B11 + A12 * B21

C12=A11 * B12 + A12 * B22

C21=A21 * B11 + A22 * B21

C22=A21 * B12 + A22 * B22

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SQUARE_MATRIX_MULRIPLE_RECURSIVE(A,B){
	n=A.rows;
	let C be a new n*n matrix;
	if(n==1){
		c11=a11*b11
	}else {
		partition A,B,and C as in equations   //采用下标的方式直接访问
		C11=SQUARE_MATRIX_MULRIPLE_RECURSIVE(A11,B11)+SQUARE_MATRIX_MULRIPLE_RECURSIVE(A12,B21);
		C12=SQUARE_MATRIX_MULRIPLE_RECURSIVE(A11,B12)+SQUARE_MATRIX_MULRIPLE_RECURSIVE(A12,B22);
		C21=SQUARE_MATRIX_MULRIPLE_RECURSIVE(A21,B11)+SQUARE_MATRIX_MULRIPLE_RECURSIVE(A22,B21);
		C22=SQUARE_MATRIX_MULRIPLE_RECURSIVE(A21,B12)+SQUARE_MATRIX_MULRIPLE_RECURSIVE(A22,B22);
	}
	return C
}