前言

本文重点回顾了卜老师课堂上关于分治算法的一些常见的问题。加油吧！ヾ(◍°∇°◍)ﾉﾞ

分治法（Divide and Conquer）

当面对一个问题的时候，我们可能一下子找不到解决问题的方法。此时，我们可以考虑将问题规模最小化，先看看当问题规模变小以后，我们如何去解决；然后逐步扩大问题的规模，看大规模的问题能不能基于小问题的解构造得到。

经过上面的思考以后，我们就可以将原问题一步步地分解为形式一致只是规模较小的问题，直到分解到规模最小化时我们能解决的程度，然后在将这些子问题的解"合并"起来构造出分解前的问题的解。

通常，分治法需要考虑3个问题。

1. 如何分解？能不能分解？采取什么样的策略将大规模问题分解为小规模问题
2. 最简单的子问题如何求解？
3. 如何基于子问题的解，得到原问题的解？

第一个问题，对于能不能分解的问题，我们一般会看问题的输入是什么样的数据结构。一般具有以下数据结构的输入是很容易分解的：

• 数组
• 矩阵
• 树
• 有向无环图
• 集合

至于如何分解，؏؏☝ᖗ乛◡乛ᖘ☝؏؏，策略也挺多的，我们即可以将问题规模按比例分解，例如一个规模为$\frac{1}{2}n$,另一个也为$\frac{1}{2}n$；
也可以将问题规模按一个规模为n-1,一个规模为1的方式分解。
一般，在分解的过程中结合随机方法，分治法一般会威力巨大，而且问题求解过程相当简洁。

而至于问题2和问题3，不同问题会有不同策略，我们视具体问题具体分析。

经典问题

下面介绍一些可使用分治法解决的经典问题。

排序问题

排序问题，我们都不会陌生，它是将一组无序的输入数据变成一组有序的数据。
输入： 一个长度为n的整数数组，$A[0,1,2,\dots ,n-1]$
输出： $A[0,1,2,3\dots ,n-1]$,且$A[i]<A[j],任意的i<j$ 。
例如:
输入 A={5,6,8,1,3,4,9,7,2}A=\{5,6,8,1,3,4,9,7,2\}A={5,6,8,1,3,4,9,7,2}
需要输出:A={1,2,3,4,5,6,7,8,9}A=\{1,2,3,4,5,6,7,8,9\}A={1,2,3,4,5,6,7,8,9}

插入排序

刚拿到这个问题，我们可能不会做，那么我们可以看问题规模最小的时候，我们会不会做。
例如n=2时，输入数组只包含2个数字。例如A2={5,6}A^{2}=\{5,6\}A2={5,6},那么我们一眼就可以看出来排序的结果为{5,6}\{5,6\}{5,6}。
当n增大的时候，我们看看怎么搞。
当n=3时，输入数组只包含3个数字，A3={5,6,8}A^{3}=\{5,6,8\}A3={5,6,8}，前面两个数字是我们刚刚解决已排序好的A2={5,6}A^{2}=\{5,6\}A2={5,6}。那我们怎么把新来的8加入这个排好序的数组呢？
可以有两种方法，一种是遍历前面已经排序好的数组，将8插入到这个排序好的数组的合适位置。遍历完5,6后，我们知道8应该在6的后面。

一种是因为前面的数组已经排序好了，那么我们可以使用二分查找，快速找到这个新元素在数组中的合适位置。二分的话，一次性就可以查到8在6的后面。
查到合适的位置之后，再将这个位置之后的元素都向后挪移一个位置，给这个元素空出那个合适的位置即可。
假设我们已经将前k个元素排序好了：Ak={a1,a2,a3,a4,…,ak}A^{k}=\{a_{1},a_{2},a_{3},a_{4},\dots,a_{k}\}Ak={a1​,a2​,a3​,a4​,…,ak​},且这些元素都是按照增序排列的。那么对于$A^{k+1}$,我们只要将$a_{k+1}$放到合适的地方就可以了。如此反复，直到k=n即可。期间，合并时候的开销主要来自：1.寻找这个数的合适位置，2.将元素后移出一个空位置。
插入排序的代码：

void insert_sort(int *A, int n)
{if (n > 2){insert_sort(A, n - 1);//将前n-1个数排序//将第n个数加入到前n-1个已排序好的数里面int i = 0;int unsorted = A[n - 1];while (A[i] <= unsorted && i<(n - 1)){i++;}if (i >= (n - 1))//说明A[n-1]比前n-1个数都大{return;}else//A[i-1]<=A[n-1],A[i]>A[n-1]{for (int j = n - 1; j >i; j--){A[j] = A[j - 1];}}A[i] = unsorted;}else if (n == 2)//只包含两个元素{if (A[0] > A[1]){int tmp = A[0];A[0] = A[1];A[1] = tmp;}}
}

算法复杂度分析：
$T(n)=T(n-1)+cn$
于是：$T(n)=O(n^2)$

归并排序

归并排序的思想其实和插入排序主要区别在于：归并排序每次将问题分解为两个规模为$\frac{1}{2}n$的子问题，而不是一个规模为$n-1$,另一个规模为$1$。这样做的好处是使得子问题的规模可以迅速降低。
代码

void merge_sort(int *A, int l, int r)
//[l,r]左闭右闭
{if (l>=r)//只包含1一个元素,则不用排序{return;}int mid = (l + r) / 2;merge_sort(A, l, mid);//左边排好序merge_sort(A, mid+1, r);//右边排好序//两个合并在一起vector<int> L;int lp = l;int rp = mid+1;while (lp <= mid && rp <= r){if (A[lp] < A[rp]){L.push_back(A[lp]);lp++;}else{L.push_back(A[rp]);rp++;}}while (lp <= mid){L.push_back(A[lp++]);}while (rp <= r){L.push_back(A[rp++]);}for (int i = l; i <= r; i++){A[i] = L[i - l];}
}

时间复杂度分析
$T(n)=2T(\frac{1}{2}n)+cn$
$T(n)=O(nlogn)$

快速排序

计算逆序对

选择第k小的数

乘法问题

矩阵乘法

最近点对

其他问题