分治和减治算法

分治法

最大子段和

基本思想：

1) 划分：将序列划在长度相等的两段
2) 求解子问题（考虑跨子段）：
2.1)将子段分成左半段和右半段
2.2)左半段从中心点处往左搜索，得到最大左子段和Suml
2.3)右半段从中心点处往右搜索，得到最大右子段和Sumr
2.4)将两个半段的子段和加起来，MaxSum=Suml+Sumr

如：
求-20，11，-4，13，-5，-22的最大子段和

解题思路：

其它基于分治法的算法有：

归并排序

快速排序

减治法

基本思想：
原问题的解可以通过规模更小的子问题的解得到，迭代缩减问题的规模，直到最后将子问题求解。

中位数问题

如：S1={11,13,15,17,19}， S2={2,4,6,8,20}，求S1∪S2={2,4,6,8,11,13,15,17,19,20}的中位数

在进行到第7步时有一个特殊情况，就是去除16前的元素却去除了16本身

折半查找

首先需要保证为升序序列

基本思想：

将待查找的数k与序列的中位数mid进行比较：
① 若k = rmid，返回结果；
② 若k < rmid，表明k在rmid往前的半段子序列中，下一步在前半段中寻找k；
③ 若k > rmid，表明k在rmid往后的半段子序列中，下一步在后半段中寻找k

程序实现：

int BinSearchch(int r[],int n,int k) {
	int low = 0, high = n - 1;
	int mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (k < r[mid]) {
			high = mid - 1;
		}
		else if (k > r[mid]) {
			low = mid + 1;
		}
		else {
			return 1;
		}
	}
	return 0;
}

时间复杂度：

最好情况：O(1)，即中值即为待查找数

最坏情况：O(log2n)

平均情况：O(log2n)

选择问题

即寻找T的第k小元素

基本思想：

1. 采用快速排序中的划分操作将无序序列分成两个子列，其中，轴值左侧子序列均比轴值小，轴值右侧子序列均比轴值大
2. 划分后，轴值所在的位置i实质上是轴值在序列按升序排序后所在的位置，即第i小
3. 比较k和i：
   ① k=i, 表示ri即为要查找的数，返回；
   ② k<i, 表明要查的数比ri小，则递归在左侧子序列找第k小；
   ③ k>i, 表明要查的数比ri大，则递归找右侧子序列找第k小。

时间复杂度：

最好情况：O(n)，即中值即为待查找数

最坏情况：O(n^2)

平均情况：O(n)

其它运用了减治法的问题

插入排序

堆排序