递归与分治

二分查找算法

template<class Type> 
int BinarySearch(Type a[], const Type& x, int l, int r){
	while (r >= l){ 
		int m = (l+r)/2;
		if (x == a[m]) return m;
		if (x < a[m]) r = m-1; else l = m+1;
	}
	return -1;
}

复杂度分析

算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了 O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。

归并排序

伪代码

void MergeSort(Type a[], int left, int right){
    if(left < right){ //至少两个元素
    	int i = (left + right) / 2; //取中点
    	MergeSort(a, left, i);
    	MergeSort(a, b, left, i, right); //合并到数组b
    	copy(a, b, left, right); //复制回数组a
    }
}

void Merge (Type a[], Type d[], int l, int m, int r){
	int i=1， j=m+1, k=1;
	while (( i <= m ) && ( j <= r)) {
		if ( c[i] <= c[j] ) d[k++] = c[i++];
		else d[k++] = c[j++];
		if ( i > m) {
			for ( int q = j; q <= r; q++ ) d[k++] = c[q];
		}
		else {
			for ( int q = i; q <= m; q++)
				d[k++] = c[q]
		}
	}
}

复杂度分析

渐进意义下的最优算法

最坏时间复杂度：O(nlogn)

平均时间复杂度：O(nlogn)

辅助空间：O(n)

快速排序

template<class Type>
void QuickSort (Type a[], int p, int r){
	if (p<r) {
        int q=Partition(a,p,r);
        QuickSort (a,p,q-1); //对左半段排序
        QuickSort (a,q+1,r); //对右半段排序
	}
}

复杂度分析

最坏情况：发生在划分过程产生的两个区域分别包含 n-1个元素和1个元素的时候。

最坏时间复杂度：

最好情况：每次划分所取的基准都恰好为中值。

最好时间复杂度：

最坏时间复杂度：

平均时间复杂度：

辅助空间： $或$

线性时间选择

Type Select(Type a[], int p, int r, int k) {
    if (r - p < 75) {
        用某个简单排序算法对数组a[p:r]排序;
        return a[p + k - 1];
    };
    for (int i = 0; i <= (r - p - 4) / 5; i++)
        将a[p + 5 * i]至a[p + 5 * i + 4]的第3小元素与a[p + i]交换位置;
    //找中位数的中位数，r-p-4即上面所说的n-5
    Type x = Select(a, p, p + (r - p - 4) / 5, (r - p - 4) / 10);
    int i = Partition(a, p, r, x),
            j = i - p + 1;
    if (k <= j) return Select(a, p, i, k);
    else return Select(a, i + 1, r, k - j);
}

上述算法将每一组的大小定为 5，并选取75作为是否作递归调用的分界点。这 2点保证了T(n)的递归式中 2个自变量之和 n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了 5 和75之外，还有其他选择。

复杂度分析

$＜$

动态规划

动态规划算法的基本要素

最优子结构

大问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。也就是说子问题的最优解构成了大问题的最优解。

在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果

通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

int LookupChain(int i，int j){
	if (m[i][j] > 0) return m[i][j];
	if (i == j) return 0;
	int u = LookupChain(i，i) + LookupChain(i+1，j) + p[i-1]*p[i]*p[j];
	s[i][j] = i;
	for (int k = i+1; k < j; k++) {
		int t = LookupChain(i，k) + LookupChain(k+1，j) + p[i-1]*p[k]*p[j];
		if (t < u) { u = t; s[i][j] = k;}
	}
	m[i][j] = u;
	return u;
}

动态规划基本步骤

1 找出最优解的性质，并刻划其结构特征（最优子结构性质）。
2 递归地定义最优值。
3 以自底向上的方式计算出最优值。
4 根据计算最优值时得到的信息，构造最优解。

⭐矩阵连乘问题

将矩阵连乘积$\begin{align}\mathcal{A}{i}\mathcal{A}{i+1}…\mathcal{A}_{j}\end{align}$ 简记为A[i:j] ，这里i≤j

考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，i≤k<j，则其完全加括号方式为：$\begin{align}\Bigl(\mathcal{A}{i}\mathcal{A}{i+1}….\mathcal{A}{k}\Bigr)\Bigl(\mathcal{A}{k+1}\mathcal{A}{k+2}…\mathcal{A}{j}\Bigr)\end{align}$

计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量

分析最优解结构

特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系

设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]

当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n

当i<j时，$\begin{align}m[i,j]=m[i,k]+m[k+1,j]+{\cal P}{i-1}{\ P}{k}{\cal P}{j}\end{align} $，这里$ A_i $的维数为$ \begin{align}P{i-1}\times P_{i}\end{align}$

可以递归地定义m[i:j]为：
$$

$$
k 的位置只有j-i种可能

计算最优值

对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有

由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法

void MatrixChain(int *p, int n, int **m, int **s) {
    //p[]存放矩阵的行和列Ai的行是p[i-1]列是p[i]，n表示n维矩阵,m[i][j]记录数乘次数,s[i][j]用于辅助构造最优解
    for (int i = 1; i <= n; i++) m[i][i] = 0; //一个矩阵数乘次数都是0
    for (int r = 2; r <= n; r++) //从2个2个乘逐渐增大子问题规模，自底向上
        for (int i = 1; i <= n - r + 1; i++) { //n-r+1是子问题个数
            int j = i + r - 1; //子问题的结束矩阵编号
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; //数乘运算次数
            s[i][j] = i; //记录在哪里断开的，表示Ai连乘到Aj的问题在i处断开了
            for (int k = i + 1; k < j; k++) { //计算不同断开方式下的数乘次数
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j]) { //如果发现更小的就替换记录信息
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
}

复杂度分析

MatrixChain的主要计算量取决于算法中对r,i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为。因此算法的计算时间上界为****。算法所占用的空间显然为。

构造最优解

void Traceback ( int i, int j, int **s ) //s是记录断开位置的矩阵
{
	if ( i == j ) return; //1个矩阵无需断开
	Traceback ( i, s[i][j], s); //从i到s前面一半内部如何继续断开
	Traceback ( s[i][j] + 1, j, s); //从s+1到j后面一半内部如何断开
	cout << “Multiply A “ << i << “,” << s[ i, j ] ; //输出前面的加括号方式
	cout << “ and A “ << ( s[ i, j ] + 1 ) << “, “ << j << endl; //输出后面的加括号方式
}

⭐最长公共子序列

若给定序列X={ }，则另一序列 Z={}，是 X的子序列是指存在一个严格递增下标序列{ }使得对于所有j=1,2,…,k有：。例如，序列Z={B，C，D，B}是序列X={A，B，C，B， D，A，B}的子序列，相应的递增下标序列为{2，3，5，7} 。

给定 2个序列 X 和 Y，当另一序列 Z既是 X的子序列又是 Y的子序列时，称 Z是序列 X 和 Y 的公共子序列。

给定2个序列X={ }和Y=Y={}，找出X和Y的最长公共子序列

分析最优解结构

设序列X={ }和Y={}的最长公共子序列为 Z={} ，则
(1) 若 x m=y n，则 z k=x m=y n，且是和的最长公共子序列。
(2) 若 x m≠y n 且 z k≠x m，则 Z 是和 Y的最长公共子序列。
(3) 若 x m≠y n 且 z k≠y n，则 Z 是 X 和的最长公共子序列。

2个序列的最长公共子序列包含了这 2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质 。

建立递归关系

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， ={ }；={ }。当i=0 或j=0时，空序列是 Xi 和 Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

计算最优值

由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

void LCSLength(int m, int n, char *x, char *y, int **c, int **b) { 
    //c[i][j]记录最优值，b[i][j]记录辅助信息用于构造最优解
    int i, j;
    for (i = 1; i <= m; i++) c[i][0] = 0; //其中一个序列为空
    for (i = 1; i <= n; i++) c[0][i] = 0;
    for (i = 1; i <= m; i++) //X序列
        for (j = 1; j <= n; j++) { //Y序列
            if (x[i] == y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1; //左上角
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2; //同一列前一行
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3; //同一行前一列
            }
        }
}

构造最长公共子序列
void LCS(int i, int j, char *x, int **b) { //只需要一个序列就可以，因为是公共子序列
    if (i == 0 || j == 0) return; //有一个序列为空
    if (b[i][j] == 1) { 
        LCS(i - 1, j - 1, x, b);
        cout << x[i]; //第i个符号就是最长子序列的最后一个符号 ，所以放在递归后面输出
    }
    else if (b[i][j] == 2) LCS(i - 1, j, x, b);
    else LCS(i, j - 1, x, b);
}

算法改进

在算法lcsLength 和lcs中，可进一步将数组 b省去。事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j] 和 c[i][j-1] 这 3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组 b而仅借助于 c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j] 和c[i][j-1] 中哪一个值所确定的。
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算c[i][j]时，只用到数组 c的第i行和第i-1行。因此，用 2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)) 。

凸多边形最优三角剖分

类似矩阵连乘问题的

用多边形顶点的逆时针序列表示凸多边形，即P= 表示具有 n条边的凸多边形。
若 vi 与 vj是多边形上不相邻的 2个顶点，则线段 vi vj称为多边形的一条弦。弦将多边形分割成 2个多边形和。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合 T 。
给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。