我们常常会遇到一些规模很大的问题，大到无从下手，不知道怎么解决。这时候怎么办，将大问题划分为小问题，小问题还不会解怎么办，那就再分，直到问题小到你会解为止。这种思想就是分治。
学习分治，就是三个字，“分”，“治”，“合”。
分(divide)：将规模为n的原问题分拆为k个小问题，每个小问题的规模都严格小于n；
治(conquer)：如果小问题的规模大于事先设定的阈值n0，则接着分，递归求解，否则直接求解小规模问题
合(merge)：将k个子问题的解组合形成原问题的解
算法复杂度
下面来看看分治算法有什么应用
问题：有n=2^k位选手参加一项单循环比赛，即每位选手都要与其他n-1位选手比赛，且在n-1天内每人每天进行一场比赛，1）设计算法以得到赛程安排；2）若比赛结果存放在一矩阵中，针对该矩阵设计O(nlogn)的算法，为各个选手赋予次序P1,P2,…,Pn，使得P1打败P2，P2打败P3，依此类推。
解
1） 设table[i][j]表示第i个人在第j天遇见的对手
n个选手分两堆
N = 2^k
假设能够对2^k-1大小的堆能够安排比赛顺序table
对于2^k 大小的矩阵
这样对原table左上角复制到右下角
左下角是左上角矩阵每一个原元素加n/2
右上角矩阵是左下角的复制
新table就是n个人的日程
基础情况
2个人的情况可解
T(n) = T(n/2) + O(n ^ 2)
T(n) = O（n^2）
分治
递归
问题解决
伪代码：
Algorithm: GameTable Input: n //n is the number of game player Output: t[][] begin{ t[][] t[][] = Table(n); return t[][]; } end function Table(int n){ if(n == 2){ t[1][0] = 1; t[2][0] = 2; t[1][1] = 2; t[2][1] = 1; return; } half = n / 2; Table(half); //left down corner matrix for(i = half + 1; i <= n; i++){ for(j = 0; j <= half; j++）{ t[i][j] = t[i - half][j] + half; } } //right down corner matrix for(i = half + 1; i <= n; i++){ for(j = half + 1; j <= n; j++）{ t[i][j] = t[i - half][j - half]; } } //right up corner matrix for(i = 0; i <= half; i++){ for(j = half; j <= n; j++）{ t[i][j] = t[i + half][j - half]; } } }2）
类似快排
拿出一个选手
赢他的选手都放前面
输的放后面
这样排完序
就是最终结果次序
Algorithm: gameRank Input: result[][] Output: a[i] //rank begin{ a[i] = {1, 2, 3 ... n}; quickSort(0, n - 1); } void quickSort(int a[], int l, int r){ int i, j, x; if(l < r){ i = l; j = r; x = a[l]; while(i < j){ while(i < j && result[a[j]][x] == 1){ j = j - 1; } if(i < j){ a[i] = a[j]; i = i + 1; } while(i < j && result[a[i]][x] == 0){ i = i + 1; } if(i < j){ a[j] = a[i]; j = j - 1; } } a[i] = x; quickSort(a, l, i - 1); quickSort(a, i + 1, r); } }
轮廓合并
已知每一个轮廓的形状，求合并后的总轮廓
分治
将n个轮廓分为两堆
每堆继续求解，继续拆分
直到分为单独的两个
这两个可以合并
类似于归并排序
T(n) = 2T(n/2) + O(m)
//m为房子x轴坐标的范围大小
O(nm)
algorithm Merge_house struct house{ int map[m]; // height on x anix } Input: house[n] Output: map; Begin{ House = Merge_house(map, 0, n -1 ); Return house; } End Merge_house(map, p, r) if p < r q = (p + r) / 2 house1 = Merge_house(map, p, q) house2 = Merge_house(map, q + 1, r) houseMerge = MERGE(map, house1, house2); return houseMerge; MERGE(map, house1, house2) for(i = 0; i < m; i++){ if(house1.map[i] > house2.map[i]){ map[i] = house1.map[i]; } else{ map[i] = house2.map[i]; } }求任意数组A中逆序对的数目，并证明算法的时间复杂性为Q(nlogn)
方法一
暴力
每一个与后面的所有比对一遍
O(n * n)
方法二
归并
将数列不断拆分
合并a[] and b[]时
如果a[i] > b[j] 则a[i]后面的与b[j]都是逆序对
逆序对数量 + （a.len() - i)
每次还是排序合并的，不然计算过的逆序对在下一次还会再算一遍
T(n) = 2(T(n/2)) + O(n)
O(nlogn)
Algorithm: backPair Input: a[n] Output: count Begin{ House = Merge_pair(a[], 0, n -1 ); Return house; } End Merge_pair(a[], p, r) if p < r q = (p + r) / 2 Merge_house(map, p, q) Merge_house(map, q + 1, r) MERGE(map, p,q, r); return houseMerge; MERGE(a, p, q, r) i = p, j = q, k = p; temp; while(i <= q && j <= r){ if(a[i] < a[j]){ temp[k] = a[i]; k++; i++; } else{ temp[k] = b[j]; count = count + q- p - i; j++; k++; } }对玻璃瓶做强度测试，设地面高度为0，从0往上有刻度1到n，相邻两个刻度间距离都相等，如果一个玻璃瓶从刻度i落到地面没有破碎，而在高度i+1处落到地面时碎了，则此类玻璃瓶的强度为i。1）若只有一个样品供测试，如何得到该类玻璃瓶的强度；2）如果样品数量充足，如何用尽量少的测试次数得到强度；3）如果有两个样品，如何用尽量少的测试次数得到强度。
1）
只有一个样品
碎了就没了
所以只有从最底层一层一层往上试
顺序查找
O(n)
2）
n个玻璃杯
任性的不行
二分查找
O(logn)
3）
两个
将楼层分组
以根号n个为一组
共根号n个组
拿出一个玻璃杯从小到大测每组的最后一个
测到碎为止
就确定在那个组
然后再那个组里找
O(根号n+根号n)
问题：已知序列S= x1,x2,…,xn以及整数k，1≤k≤n，试查找S中第k小的数。
方法1
找最小数，找k次
O(kn)
方法2
类似于快排
找一个数
能找到它的位置
位置与k比较
知道下一次要找的范围
一次缩小1/2
Algorithm: k-min Input a[] Output ans begin { ans = select(k, 1, n); } end function select(k, left, right){ x = a[left] add = x address of ordered array if(k > add){ select(k, add, right) } else{ select(k, left, add); } }总结
分治，分而治之，然后再合并。是不是还有一种帝王君临天下的感觉，其实一样啊，国家那么大，帝王管不过来啊，分呗，分成一个个郡，皇亲将相帮着管，然后每个郡再合并到中央管，也是分治的思想啊。
