减治法利用了一个问题给定的实例的解和同样问题较小实例的解之间的关系，从较小实例出发，利用迭代，或者从较大的实例出发，利用递归，从而求解

减常量形式
减常因子形式
减可变因子形式

减一技术：问题的较小实例与较大实例的规模相差一个常数，通常这个常数为：1

减常量形式

eg. 插入排序

对一个包含 N 个元素的数组进行排序

假设这个数组的较小规模包含 N-1 个元素的子数组已经按照从小到大的顺序进行排序，则此时求解即求解如何将第 N 个元素也加入数组，使得这 N 个元素是有序的？

即：将第 N 个元素插入已经有序的数组中，使得最终的数组有序

可以从右到左扫描已经有序的子数组：

如果扫描到的元素比第 N 个元素大，那么插入的位置至少应该在扫描元素之前，那么就让扫描元素向右覆盖，将第 N 个元素插入当前扫描位置，然后继续扫描
如果扫描到的元素比第 N 个元素小，那么就应该结束扫描，将第 N 个元素插入当前扫描位置之后一个的位置

InsertSort(A[0, ..., n-1])

// 用插入排序对给定数组排序
// 输入：一个可排序的数组 A
// 输出：非降序排列数组 A

for i⬅1 to n-1 do {
    v ⬅ A[i];
    j ⬅ i-1;
    while(j>=0 and A[j]>v) {
        A[j+1] ⬅ A[j];
        j ⬅ i-1;
    }
    A[j+1] ⬅ v;
}

时间复杂度分析：

基本操作：子数组扫描

最坏情况：数组是从大到小排序的

$C_{worst}(n) = \sum_{i=1}^{n-1} \sum_{j=0}^{i-1} = \sum_{i=1}^{n-1}i = \frac{(n-1)n}{2} \in \Theta (n^2)$

最好情况：数组是从小到大排序的

$C_{best}(n) = \sum_{i=1}^{n-1}1 = n-1 \in \Theta (n)$

随机排序的数组

$C_{avg}(n) \approx \frac{n^2}{4} \in \Theta (n^2)$

平均比较次数是最坏情况的一半：$\frac{n^2}{4 }$

eg. 生成组合对象

旅行商问题：需要生成包含所有城市的所有排列

eg. 集合 (1, 2, 3) 的排列有 6 个，分别为：123，132，213，231，312，321

用减一法的思路来解决对 n 个元素生成排列的问题：

假设生成较小规模的集合 {1, …, n-1} 的全部 (n-1)! 个排列的问题已经解决，我们只需要把 n 插入到每个排列的 n 个可能的位置中去，问题就可以解决，由于每个排列插入 n 之后，是 n 个不同的排列，原始问题的排列数则为：n(n-1)!，即：n!

满足最小变化要求： 假设插入第一个排列时从右到左，插入下一个排列时从左到右，得到的排列中相邻两个只有两个元素是不同的，这样交换相邻排列中的两个元素就可以得到一个新的排列

缺点：

需要保存 n-1 规模子集的全部排列，才能产生出 n 规模自己的排列，比较浪费存储空间

改进：

Johnson-Trotter 算法：从原始排列开始，通过交换排列中某两个相邻的元素来产生一个新的排列，如此生成全部排列

规定排列中每个元素都有一个方向，我们在元素上画一个箭头，箭头指向元素移动的方向，如果箭头指向一个相邻的较小的元素，则称该元素是可移动的，如果一个元素在排列的左端，箭头方向也向左，或者一个元素在排列的右端，箭头方向也向右，则称该元素是不可移动的

步骤：

初始化排列为：1, 2, 3, …, n，每个元素的方向向左；
如果排列中存在可移动元素，执行步骤 3，否则退出；
在排列中找出最大的可移动元素；
将该元素与其所指向的元素进行交换；
调换所有大于该元素的元素的方向；
输出交换元素之后的排列，返回步骤 2。

由于该算法的运行时间与排列数量成正比，所以其时间复杂度为：n!

缺点：生成的排列次序不是字典序

改进：算法 LexicographicPermute

以字典许生成排列的步骤：

初始化排列为：1, 2, 3, …, n；
如果排列中有两个连续升序的元素，则执行步骤 3，否则退出；
找出所有两个升序元素对 $a_{i}<a_{i+1}$ 中索引最大的为 i，则 $a_{i+1}, …, a_{n}$ 称为最长递减后缀；
找到最长递减后缀中大于 $a_{i}$ 的最小元素，即：找到使得 $a_{i}<a_{j}$ 的最大索引 j；
交换 $a_{i}$ 和 $a_{j}$；
将新后缀 $a_{i+1}, …, a_{n}$ 颠倒，变为递增的；
输出最后的排列，返回步骤 2。

减常因子形式

与减常量形式不不同，减常因子减去的是某一个固定比例的实例，比如：原实例的一半

eg. 折半查找

将数组分成两半，比较待查找的键 K 和数组最中间的元素的大小关系，如果 K 大于 A[0], …, A[m], …, A[n-1]，则在后一半数组中继续查找，否则在前一半数组中继续查找，查找方式相同，知道找到元素或者数组无法分半为止

步骤：

比较数组中间元素即下标为 m 的元素和键值 K 的大小关系，确定下一次查找的子数组的左右边界；
在新的子数组中查找，直到找到元素或者子数组长度为空。

时间复杂度分析：

因为每次比较数组长度都需要减少一半，设数组长度为 $2^k$，那么最坏的情况需要 k+1 次，就可以将数组长度折半到 1，此时比较次数为：$\log_{n+1}$，复杂度渐进函数为：$\log_{n}$

eg. 约瑟夫斯问题

将 n 个人从 1 编号到 n 并围成一圈，从 1 开始依次去掉第二个人，知道只剩一个人，求留下的人的编号是多少？

用 J(n, 2) 表示 n 个人，去掉每两个人中的后一个，最后剩下的人的编号

假设 n=6，那么第一圈去掉的编号是 2, 4, 6，第二圈去掉的编号是 1, 3，最后剩下的编号是 5，即：J(6， 2)=5

又假设 n=7，则 J(7, 2)=7

当 n 为偶数：J(2k) = 2J(k)-1

当 n 为奇数：J(2k+1) = 2J(k)+1

简便求解：将 n 转换为二进制数，然后将二进制数循环左移 1 位，新的二进制数转换为十进制数，这个十进制数就是问题的解

eg. J(6) = J(1102) = 1021 = 5

减可变因子形式

即：减可变规模算法，减去的实例规模是不固定的

eg. 快速选择算法

求 n 个数列表的第 k 个最小元素

思路：

如果针对数列的第一个元素，可以将数列分成：

包含了数列中小于第一个元素的若干元素
数列中的第一个元素
大于第一个元素的若干元素

经过划分就可以得知第一个元素是数列中第几小的元素，假设第一个元素 S，根据 k 和 S 的大小关系，可以选择继续在大于或者小于 S 的子数列中继续划分子数列，直到 S=k

通过划分就可以将问题的实例不断减小，且减小的规模不是固定的一个数值或者比例，而是可变化的，由于划分快速将实例规模变小了，并且选择了小规模实例继续进行划分，即：快速选择算法

效率分析：

最好情况：一次划分就找到指定元素，$T(n) = n-1 \in \Theta (n)$

最坏情况：经过 n-1 次划分才找到指定元素，$T(n) = (n-1) + (n-2) + … + 1 = \frac{(n-1)n}{2} \in \Theta (n^2)$

平均情况：$T(n) = T(\frac{n}{2}) + (n+1) \in \Theta(n)$

对于选择问题，可以直接用排序方法求得一个有序数组，然后输出指定位置的元素，排序方法中有的算法效率比 $n^2$ 低，似乎基于排序的方法比快速选择算法更优，但是：快速选择算法在平均情况下的效率是线性的，优于基于排序的方法

TUFZ's Blog

减治法与排序