算法设计与分析复习总结（二）

第二章 递归与分治策略

分治法的适用条件

1.该问题的问题规模缩小到一定程度就可以轻松解决
2. 可以分解为若干个规模较小的相同问题，具有最优子结构性质，这条是使用分治法的前提。最优子结构性质的含义是问题最优解包含子问题最优解。
3. 利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征而不具备第三条特征，则可以考虑贪心算法或者动态规划
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

分治算法的复杂性分析

注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当$m^i\le n<m^{i+1}$时，$T(m^i)\le T(n)<T(m^{i+1})$。

二分搜索技术

例题

用二分查找算法实现：判断$m\times n$矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。如图所示：

#include<vector>
using namespace std;
clssic Solution{
public:bool searchMatrix(vector<vector<int>>& matrix, int target){if(matrix.empty() || matrix[0].empty()){return false;}int m=matrix.size(), n=matrix[0].size();int left=0,right=m*n-1;int mid=(right-left)/2;int row=mid/n, col=mid%n;if(matrix[row][col]==target){return true;}else if(matrix[row][col]>target){right=mid-1;}else{left=mid+1;}return false;		
}
};

大整数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序和快速排序

线性时间选择

最接近点对问题

循环赛日程表