网站建设项目经历,网页转微信小程序,品牌推广图片,广东省政务服务网分治法
将一个难以直接解决的大问题#xff0c;分割成一些规模较小的相同问题#xff0c;以便各个击破#xff0c;分而治之。最好使子问题的规模大致相同。
分解#xff08;Divide#xff09;#xff1a;将一个难以直接解决的大问题#xff0c;分割成一些规模较小的子…分治法
将一个难以直接解决的大问题分割成一些规模较小的相同问题以便各个击破分而治之。最好使子问题的规模大致相同。
分解Divide将一个难以直接解决的大问题分割成一些规模较小的子问题这些子问题互相独立且与原问题相同。递归求解子问题若问题足够小则直接求解。将各个子问题的解合并得到原问题的解。
求二叉树深度
int get_depth(BTPtr pbt){int dL,dR0;if(pbt NULL){return 0;}if((!ptb-lchild) (!ptb-rchild)){return 1;}dL get_depth(pbt-lchild);dR get_depth(pbt-rchild);return 1 ((dLdR)?dL:dR);
}分治法所能解决的问题一般具有四个特征
该问题的规模缩小到一定的程序就可以容易地解决。该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质。利用子问题的解可以合并得到原始问题的解。各个子问题是相互独立的。
二分搜索技术每执行一次算法while循环待搜索数组的大小减少一半因此最坏时间复杂度O(log n)
int BinarySearch(int a[],int x,int left,int right){while(left right){int mid (left right)/2;if(a[mid] x){return mid;}else if(a[mid] x){left mid 1;}else{right mid - 1;}}return -1;
}Master定理递归复杂度判定定理 大整数的乘法将两个n位大整数相乘 传统逐位相乘、错位相加的传统方法O(n2)效率太低。 分治法将该问题分解为若干个规模较小的相同问题。 为了降低时间复杂度必须减少乘法的次数。 两个XY复杂度都相同但ab,cd可能得到(n/2)1位的结果使问题的规模变大故不选择第2种方案。
矩阵乘积的传统算法时间复杂度O(n3)
void multi(int A[],int B[],int C[]){for(int i1; in ;i){for(int j1;jn;j){C[i][j] 0;for(int k1 ;kn; k){C[i][j] A[i][k]*B[k][j];}}}
}分治法矩阵乘法 为了降低时间复杂度必须减少乘法的次数。 棋盘覆盖问题在一个2kx2k个方格组成的棋盘中要求用图(b)所示的4种L形态骨牌覆盖给定的特殊棋盘覆盖给定特殊棋盘上除特殊方格以外的所有方格任何2个L型骨牌不得重叠覆盖。 分治策略技巧使每个子棋盘均包含一个特殊的方格从而将原问题分解为规模较小的棋盘覆盖问题。 棋盘覆盖问题中数据结构的设计
棋盘用二维数组board[size][size]表示一个棋盘其中size2k。为了在递归处理的过程中使用同一个棋盘将数组board设为全局变量。子棋盘在棋盘数组board[size][size]中用子棋盘左上角的tr、tc和棋盘边长s表示。特殊方格用board[dr][dc]表示dr和dc是该特殊方格在棋盘数组board中的下标。L型骨牌一个2k×2k的棋盘中有一个特殊方格所以用到L型骨牌的个数为(4k-1)/3将所有L型骨牌从1开始连续编号用一个全局变量t表示。
void ChessBoard(int tr,int tc,int dr,int dc,int size){if(size 1) return; //棋盘只有一个方格且是特殊方格。t;//L型骨牌号已经初始化为0。s size/2;//划分棋盘if(drtrs dctcs){ //特殊方格在棋盘左上角ChessBoard(tr,tc,dr,dc,s);}else{ //用t号L型骨牌覆盖右下角再递归处理子棋盘board[trs-1][tcs-1] t;ChessBoard(tr,tc,trs-1,tcs-1,s);}if(drtrs dc tcs){ChessBoard(tr,tcs,dr,dc,s);}else{board[trs-1][tcs] t;ChessBoard(tr,tcs,trs-1,tcs,s);}if(drtrs dctcs){ChessBoard(trs,tc,dr,dc,s);}else{board[trs][tcs-1] t;ChessBoard(trs,tc,trs,tcs-1,s);}if(dr trs dc tcs){ChessBoard(trs,tcs,dr,dc,s);}else{board[trs][tcs] t;ChessBoard(trs,tcs,trs,tcs,s);}
}当k0时将2的k次幂乘以2的k次幂分隔成为4个2的k-1次幂乘以2的k-1次幂子棋盘。特殊方格必位于4个较小棋盘之一中其余3个子棋盘中午特殊方格。为了将这3个特殊方格的子棋盘转化为特殊棋盘可以用一个L型骨牌将这3个较小棋盘的汇合处覆盖这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格从而将原问题转换成4个较小规模的棋盘覆盖问题。递归地使用这种分割直至棋盘简化为1*1棋盘。 快速排序在数组中确定一个记录作为划分元将数组中关键字小于划分元的记录移动到划分元之前将数组中大于划分元的记录移动到划分元之后。
int Partition(int *arr,int L,int R){int left L;int right R;int pivot arr[left];while(left right){while(leftright arr[right]pivot)right--;if(left right){arr[left] arr[right];}while(leftright arr[left]pivot)left;if(leftright){arr[right] arr[left];}if(left right){arr[left] pivot;return left;}}
}void QuickSort(int *arr,int L,int R){if(L R){int position Partition(arr,L,R);quickSort(arr,L,position-1);quickSort(arr,position1,R)}
}最好情况T(n)O(nlogn)每次总是选到中间值作为划分元 最坏情况T(n)O(n2)每次总是选到最小或最大元素作为划分元 算法性能与系列中关键字的排列顺序和划分元的选取有关
当初始序列按关键字有序正序或逆序时快速排序蜕化为冒泡排序此时算法性能最差时间复杂度为O(n2)。可以用“三者取中”法来选取划分元设数组首记录为r[s]、尾记录为r[t]取r[s]、r[t]和r[(st)/2]三者的中间值为划分元。也可采用随机选取划分元的方式
快速排序算法的性能取决于划分的对称性。通过修改算法partition可以设计出采用随机选择策略的快速排序算法。在a[p:r]中随机选出一个元素作为划分基准这样可以使划分基准的选择是随机的从而可以期望划分是比较对称的。
int RandomizedPartition(int a[],int p,int r){int i random(p,r);swap(a[i],a[p]);Partition(a,p,r)
}线性时间选择给定线性序集中n个元素和一个整数k要求找出这n个元素中第k小的元素问是否可以在O(n)时间内得到解决可以采用分治法模仿快排对输入数组进行递归划分只对划分出的子数组之一进行递归处理子数组的选择与划分元和k相关。
int RandSelect(int A[],int start,int end,int k){if(start end){return A[start];}int i RandomizedPartition(A,start,end);int n i-start1;//左子数组的个数if(k n){RandSelect(A,start,n,k);}else{RandSelect(A,i1,end,k-n;)}
}线性时间内找到合理划分基准的步骤select函数
将n个元素划分成n/5个组每组5个元素只有可能一个组不是5个元素。用任意一种排序算法对每组中的元素排序。取出每组中的中位数共n/5个元素。递归调用select函数找出这n/5元素中的中位数。如果n/5为偶数就选择2个中位数中较大的一个以这个选出的元素作为划分基准。
按递增序列找出下面29个元素的第18个元素 8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.
把前面29个元素分为6组ceil(29/5)(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7),(23,22,46,29).提取每一组中的中值元素构成集合{33,49,13,25,16,29}递归地使用该算法求得集合中的中值得到m29.根据m29把29个元素划分为3个子数组P{8,17,4,11, 3,13,6,19, 25,16,5,7,23,22}Q{29}R{31,60,33,51,57,49,35,43,37,52,32,54,41,46}P中有14个元素Q中有1个元素所以18-153对R递归地执行本算法。将R划分成3组ceil(14/5):{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46}求取这3组元素的中值元素分别为{514346}这个集合的中值是43.根据43将R划分成3组{31, 33, 35,37,32, 41},{43},{60, 51,57, 49, 52,54, 46}因为k3第一个子数组的元素个数大于k所以放弃后面两个子数组以k3对第一个子数组递归调用本算法将这个子数组分为5个元素为一组 {31,33,35,37,32}、{41}取中值为33。根据33把第一个子数组划分成{31,32},{33},{35,37};因为k3,而第一、第二个子数组的元素个数为3所以33即为所求取的第18个小元素。
int Select(int a[],int start,int end,int k){if(end-start75){//用某个简单的算法对数组a[start:end]排序return a[startk-1];}for(int i0; i(end-start-4)/5; i){//将a[start5*i]与a[start45*i]的第3小元素与a[starti]交换位置}//找出中位数中的中位数int x Select(a,start,start(end-start-4)/5,(end-start-4)/10);int i Partition(a,start,end,x); //划分元位置int n i-start1; //左数组长度if(k n) return Select(a,start,i,k);else{return Select(a,i1,end,k-n);}
}最接近点对给定平面上的n个点找出其中的一对点使得在n个点组成的所有点对中该点对的距离最小。
直观解法将每一个点与其他n-1个点的距离算出找出最小距离时间复杂度T(n)n(n-1)O(n2) 分治法
分解将n个点的集合分成大小近似相等的两个子集。求解递归求解两个子集内部的最接近点对。合并从子空间内部最接近点对和两个子空间之间的最接近点对中选择最接近点对。
分治法
假设我们用x轴上某个点m将S划分为2个子集S1和S2基于平衡子问题的思想用S中各点坐标的中位数来作分割点。递归地在S1和S2找出其最接近点对{p1,p2}和{q1,q2}。设dmin{|p1-p2|,|q1-q2|}则S中的最接近点对可能是{p1,p2}或者是{q1,q2}或者是某个{p3,q3}其中p3∈S1且q3∈S2。如果最接近点对是{p3,q3}即|p3-q3|d即p3和q3两者之间的基于不超过dp3∈(m-d, m]q3∈(m, md]。
bool Cpair1(S,d){n |S|;if(n 2){d ∞;return false; }m S中各点坐标的中位数。构造S1和S2 //构造S1{x S|xm}, S2{x S|xm}Cpair(S1,d1);Cpair1(S2,d2);p max(S1);q min(S2);d min(d1,d2,q-p);return true;
}考虑二维的情况
选取二维平面的一条垂直线Lxm作为分割线其中m为S中各点x坐标的中位数由此将S分割成S1和S2。递归地在S1和S2上找出其中最小距离d1,d2。设dmin{d1,d2}S中的最接近点对间的距离或者是d或者是某个点对{p,q}之间的距离其中p∈S1且q∈S2。如果用符号P1和P2分别表示直线 L 的左右两边宽为d的区域则必有p∈P1且q∈P2 考虑P1中任意一点p它若与P2中的点q构成最接近点对的候选者则必由distance(p,q)dP2中满足条件的点一定落在矩形R中矩阵R的大小为dx2d。 由d的定义可知P2中任何2个点qi∈S的距离都不小于d由此可以推出矩形R中最多只有6个S中的点。 在分治法的合并步骤中最多只需要检查6×n/23n个候选者
