201-递归与分治策略

分支法思想：分+治+合

上图以 $T(n)=4T\left(\frac{2}{n}\right)$ 为例

分治法的设计思想是，将一个难以解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之

分治法

• 分治法产生的子问题是原问题较小模式
• 反复应用分治手段，可以使子问题规模不断缩小
• 最终使子问题缩小到很容易求出其解
• 将规模较小问题的答案逐级向上合并，可得大问题的方案

分治法解决问题通常使用递归算法 直接或间接的调用自身的算法为递归算法

递归的概念

递归的算法框架

例 1 阶乘函数

阶乘函数可递归定义为：

$$n!=\{\begin{array}{ll}1& n=0\\ n(n-1)!& n>0\end{array}$$

边界条件与递归方程是递归函数的两个要素 递归函数只有具备了这两个要素，才能在有限次计算后的出结果

$n!$ 可递归的计算如下：

int fact(int n)
{
	if (n==0) return 1;
	else return n* fact(n-1)
}

例 2 斐波那契数列

例 3 Ackerman 函数

前三个是边界情况，第四个是递归

前两例中的函数都可以找到相应的非递归方式定义

Ackerman 函数找不到非递归的定义，只能使用递归函数实现 一个问题有递归和非递归定义，可使用递归或给递归算法实现

例 4 排列问题

设计一个递归算法生成 n 个元素 $\{r_1,r_2,\dots ,r_n\}$ 的全排列 Ps: 全排列是指阶乘的因子, 如 (1，2，3，4)

这里递归的得到数列，从 （n）→(n-1, n)→ (n-2, n-1, n) 依次下去

例 5 汉诺塔问题

算法描述

void hanoi(int n, int a, int b, int c) 
/*   把n个盘子从 a柱 移动到 b柱，借助c柱中转 */
{
	if(n>0)
	{
		hanoi(n-1, a, c, b)  //把a柱 除了最下面的盘子全都移到c上
		move(a, b)  //把 a柱最下面的盘子 移到 b柱	， 这样完成了一个盘子的移动
		hanoi(n-1, c, b, a)  // 剩下的盘子继续递归移动；
	}
	//n=0时结束
}

递归小结

优点： 结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便

缺点： 递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多

建议： 1. 能用递推算法解决，就不要用递归算法 2. 用栈模拟的非递归算法，对运行效率改善有限，不建议使用

分治法的适用条件

分治法能解决的问题一般具有以下几个特征

1. 该问题的规模缩小到一定的程度就可以容易的解决
2. 该问题可以分解成若干个规模较小的相同问题
3. 利用该问题分界处的子问题的结可以合并成该问题的解
4. 该问题所分解出的各个子问题是相互独立的

其中 2，3 条表明子问题的最优解和该问题的最优解是一致的，这是最优子结构性质； 第4 条表明，分解出来的子问题是不重复的，共同组成该问题的解，这是无重复子问题

最优子结构性质和无重复子问题是分支法所能解决问题的必备要素

分治法的基本步骤

当问题规模足够小的的时候直接处理，否则把问题划分为多个规模相近的子问题，在逐个解决子问题，最后合并答案

分治法的复杂性分析

分治法将规模为 n 的问题分成 l 个规模为 n/m 的子问题去解

1. 设分解阈值 n=1 且 adhoc 解规模为 1 的问题耗费 1 个单位时间
2. 设将原问题分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需要用f（n）个单位时间
3. 用T（n）表示分治法解规模为|P|=n 的问题所需的计算时间

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ kT\left(\frac{n}{m}\right)+f(n)& n>1\end{array}$$

二分搜索技术

非递减序的 n 个元素 $a[0:n-1]$，现在要在这个元素众找出一特定元素x

分析： 初始用 l、r 分别表示整个数组最左边和最右边的数据索引 一个子问题 $a[l:r]$，r<l 是表示没有任何元素，返回-1 - 设在 $a[l:r]$ 中找到 x，mid=(l+r)/2 1. 如果 $x==a[mid]$，则找打 2. 如果 $x<a[mid]$，继续在 $a[l,mid]$ 中找 x 即可，即令 r=mid 3. 如果 $x>a[mid]$，继续在 $a[mid,r]$ 中找 x 即可，即令 l=mid 子问题的答案就是大问题的答案，满足分支的四个适用条件

算法描述

递归算法时间复杂度分析 时间复杂性的递归方程

$$T(n)=\{\begin{array}{ll}1& n=0\\ T\left(\frac{n}{2}\right)+1& n>1\end{array}$$

利用主定理或递归树可以求其时间复杂性为 $O(\log n)$

非递归算法时间复杂性分析 每执行一个循环，问题规模减半，即使最坏情况下，时间复杂性为 $O(\log n)$

虽然时间复杂度非递归方案和递归方案一样，但是非递归方案效率更高

快速幂算法

给定实数 a 和非负正数 n。用分治法设计求 $a^n$ 的快速算法（递归算法）

分析

这里把求 $a^n$ 转化成求 $a^{\frac{n}{2}}$ 的问题，缩小了问题规模，且可以和成该问题的解，见上递归公式，符合使用条件 1，2，3; 且每次递归 $\frac{n}{2}$ ，问题相互独立；满足四个条件

时间复杂性 $O(\log n)$

非递归算法

Strassen 矩阵乘法

传统方法需要 3 层循环遍历两个矩阵中的元素，时间复杂度为 $O(n^3)$

划分之后变成 8 个子问题，每个子问题变成 $\frac{n}{2} * \frac{n}{2

复杂性分析

$$T(n)=\{\begin{array}{ll}O(1)& n=2\\ 8T\left(\frac{n}{2}\right)+O(n^2)& n>2\end{array}$$

这里的 f (n) 是 $O(n^2)$，是因为 $C_{11}$ 等四个子问题中，还需要进行一次加法 $\frac{n^2}{4}$

$T(n)=O(n^3)$ 没有改进 $\Theta$ (主定理规则 1）

改进

这样 $M_1{M}_7$ 还是 $\frac{n}{2}\ast \frac{n}{2}$ 的问题，减少了一次相乘

改进的复杂度分析 $T(n)=O(n^{\log 7})=O(n^{2.81})$ ✔较大改进

$$T(n)=\{\begin{array}{ll}O(1)& n=2\\ 7T\left(\frac{n}{2}\right)+O(n^2)& n>2\end{array}$$

棋盘覆盖问题

在一个 $2^k\times 2^k$ 个方格组成的棋盘之中，恰有一个方格与其他方格不同，成该方格为-特殊方格。且称该棋盘为-特殊棋盘。棋盘覆盖问题中，要用图示的 4 中不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖

思路

当 k>0 是，将 $2^k\times 2^k$ 棋盘分割为 4 个 $2^{k-1}\times 2^{k-1}$ 子棋盘（a）所示。特殊方格必位于较小子棋盘之中，其余 3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用 L 型骨牌覆盖这 3 个较小棋盘的会合处，如图（b）所示，从而将原问题转化为 4 个较小规模的棋盘覆盖问题。递归的使用这种分割，直到棋盘简化为棋盘 $1\times 1$

原棋盘分割成 4 个，在三个无特殊方格的棋盘添加一个 L 型骨牌，问题变成了 4 个和原问题相同性质的 4 个子问题

算法描述

其中 tr，tc 是左上角坐标，dr，dc 是特殊方格坐标，size 是棋盘大小, s 是子棋盘大小 四个 if 对应特殊方格在不同子棋盘中的情况

时间复杂性

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ 4T\left(\frac{n}{2}\right)+O(1)& n>1\end{array}$$

有主定理规则 1 ，可得时间复杂性 $T(n)=O(n^2)$

本算法可使用队列或者栈实现非递归算法

拓展

队列实现 队列先入先出

入队：一个大棋盘分为四个子棋盘，将四个子棋盘按序入队

出队：从队列中取出一个棋盘，将其分为四个子棋盘

注意：划分为四个子棋盘时，一个 L 型块被放入到棋盘中

栈实现 栈先入后出

入栈： 大棋盘分为四个子棋盘，将四个子棋盘按序入栈

出栈：从栈顶取出一个棋盘，将其分为 4 个子棋盘

注意划分为四个子棋盘时，一个 L 型块放到棋盘中

总结

1. 三种算法的覆盖图案不同
2. 如果原始途中的已覆盖方格位置不同，导致覆盖图案也不同
3. 如果四个子问题的处理顺序不同，覆盖方案也不同
4. 三种算法运行效率比较：栈运行时间最短，队列运行时间最长

合并排序

将待排序元素集合分成大小大致相同的 2 个子集合，分别对 2 个子集合进行排序，最终将排好序的子集合合并成一个有序结合

算法实现（递归）

void MergeSort(Type a[], int left, int left)
{
	if (left < right) // 至少两个元素
	{
		int i=(left+right)/2; //取中点
		MergeSort(a,  left, i);   // 左半部分
		MergeSort(a, i+1, right);	// 右半部分
		merge(a, b, left, i, right);		//两个部分排序合并， 放到临时数组b中
		copy(a, b, left, right);		// 把数组b复制回 数组a
	}
}

复杂度分析

$$T(n)=\{\begin{array}{ll}O(1)& n\le 1\\ 2T\left(\frac{n}{2}\right)+O(n)& n>1\end{array}$$

$T(n)=O(n\log n)$ 渐进意义下的最优算法

非递归-归并排序

非递归算法情况下，从最底层两个元素开始归并，变成每两个相邻序列归并，最终合成整个序列

非递归算法复杂性分析 最坏时间复杂度：$O(n\log n)$ 平均时间复杂度：$O(n\log n)$ 辅助空间：$O(n)$ 稳定性：稳定

快速排序

快速排序是对冒泡排序的一种改进方法

其中 Partition 函数按照枢轴元素，把数据放在枢轴元素左右

**快速排序算法的时间复杂型分析

• 快速排序算法的性能取决于划分的对称性 最坏的情况：每次划分成 2 个子问题，一个长度为 0. 另一个长度为 n-1，其对应的递归定义为：

T(n)=\begin{cases} 1 & n=1 \ T(n-1)+n &n>1 \end{cases}

最坏的时间复杂度：$O(n^2)$ 平均时间复杂度：$O(n\log n)$ 稳定性：不稳定 改进：舍伍德算法（第七章） 通过修改算法 partition，可以设计出来采用随机策略的快速排序算法，可以在 $a[p,r]$ 中堆积一个元素作为划分基准，可以期望划分是较对称的 **算法描述** ```cpp template <class Type> int RandomizedPartition(Type a[], int r) { int i = Random(p, r); // 随机一个在p,r之间的索引 Swap(a[i], a[p]); //把随机的元素作为枢轴元素 return Partition(a, p, r); } ``` ## 拓展 ### 常规 Partition 算法（2-way）的缺点  如上图，当序列中重复元素过多时，我们希望如果枢轴元素是重复元素，重复元素不要在出现在子问题中 ### 改进 Partition 算法（3-way）的设计  > 额外返回枢轴元素重复部分的前后索引，方便子问题跳过这一部分数据，这样提高了算法效率 > > 具体算法，需要保证 p，r 之间的元素是枢轴元素，把不是枢轴元素的根据和枢轴元素的大小比较，放到 p 或者 r，随后收紧 p 或 r 的范围 根据 $a[k]$ 与 x 比较结果有三种不同的动作  > 其中 k 是扫描索引，一开始 p，r 作为序列前后端的索引，随着 k 的扫描，p，r 之间逐渐收紧，最后 p, r 之间只有枢轴元素 > 当 k 索引的元素比枢轴元素小的时候，这个数据和 p 交换位置，且 p++, k++ > 当 k 索引的元素比枢轴元素大的时候，这个数据和 r 交换位置，且 r--，k 不变 ### 改进算法的代码  > 其中 p，r 使用引用，这两个数据需要回传 ### 可利用改进 partition 的算法 1. 快速排序 2. 线性时间找第 k 小 | **自己完成** 3. 求众数问题| **自己完成** **快速排序-程序演示**  > 主函数包含 threep 函数的测试，使用时注释掉，并且打开下面快排和打印的两行程序 ### 演示（以快速排序为例） Dev 运行上述代码，略 # 线性时间选择算法 给定线性序集中 n 个元素和一个正数 k, $1\leq k\leq n$，要求找出这 n 个元素中第 k 小的元素 **算法描述** ```cpp template <class Type> Type RandomizedSelect(Type a[], int p, int r, int k) { if (p==r) return a[p]; int i = RandomizedPartition(a, p, r); j = i-p+1; if (k<=j) return RandomizedSelect(a, p, i, k); else return RandomizedSelect(a, i+1, r, k-j) } ``` > 每次使用 partition 算法分组，向着元素所在的分组前进 **时间复杂性** 在最坏情况下，算法 RandomizeSelect 需要 $O(n^2)$ 计算时间。但可以证明，算法 RandomizeSelect 可以在 $O(n)$ 平均时间内找出 n 个输入素元素中第 k 小元素 # 循环赛日程表  > 左上和右下的、右上和左下是相同的，大的表格可以分成两个子问题，同时子问题和问题有相同的性质 **算法描述**  **递归算法复杂性分析** 递归公式：

T(n)=2T\left( \frac{n}{2} \right)+ \frac{n^2}{2}

$n^{\log_{b}a}=n^{\log_{2}2}=n, f(n)=O(n^2)$, 满足主定理规则 3 ： $T(n)=O(f(n)) = O(n^2)$ **非递归算法** 直接把第一列 1 x 1交叉复制到第二列，再把前两例 2 x 2交叉复制到三四列，依次进行 # 小结 1. 使用分治策略解决问题时，注意检查四个条件是否满足 2. 尽量保证划分出的子问题规模大致一致。平衡子问题思想 3. 如果可以使用递归的方式解决问题，尽量使用递归算法 4. 递归的分治算法的时间复杂性分析，要先写出其时间复杂性的递归方程，然后用主定理或递归树解方程 5. 用递归算法解决问题是，要分析出其边界条件和递归方程（过程）