广州在线网站制作推荐,企业团建公司,公司网站icp备案,海宁高端高端网站设计分治算法
用于设计算法的一种常用技巧–分治算法#xff08;divide and conquer#xff09;。分治算法由两部分组成#xff1a; 分(divide)#xff1a;递归然后借机较小的问题#xff08;基础情况除外#xff09;治(conquer)#xff1a;然后从子问题的解构建原问题的解…分治算法
用于设计算法的一种常用技巧–分治算法divide and conquer。分治算法由两部分组成 分(divide)递归然后借机较小的问题基础情况除外治(conquer)然后从子问题的解构建原问题的解 分治算法一般在主题逻辑中都至少含有两个递归调用的例程而正文中只有一个递归调用的例程不算是分治算法。一般坚持子问题是不想交的即不重叠
前几章中分治算法
之前我的文章中我们依据看到有几个分支算法比如 排序算法中的快速排序二叉树中的树的遍历
案例分析
最大子序列求和问题
给定包含有负数的整数A1 A2 A3…AN求解该集合中子序列的和的最大值∑kij\sum_{ki}^j∑kijAk此问题最简单的方式暴力双循环在这种情况下算法逻辑简单但是时间复杂度达到了O(N^2)如下代码实现
/*** author liaojiamin* Date:Created in 16:38 2021/1/29*/
public class MaxSumRec {public static int[] getArrayData(int size) {int[] arrayData new int[size];Random random new Random();for (int i 0; i size; i) {int temp random.nextInt(50);if (temp 25) {arrayData[i] temp;} else {int value temp - 2 * temp;arrayData[i] value;}}return arrayData;}/*** fun1 双循环 时间复杂度O(N^2)* */public static int getMaxSumRec(int[] arrayData){if(arrayData null || arrayData.length 0){return -1;}if(arrayData.length 1){return arrayData[0] 0 ? arrayData[0] : -1;}int max 0;for (int i 0; i arrayData.length; i) {int sum 0;for(int ji; j arrayData.length; j){sum arrayData[j];if(sum max){max sum;}}}return max;}public static void main(String[] args) {int[] arraydata getArrayData(20);for (int i 0; i arraydata.length; i) {System.out.print(arraydata[i] , );}System.out.println();System.out.println(getMaxSumRec(arraydata));}
}但是显然这不是最优的解法对应这个存在复杂度为ONlogN的解法我们如下描述。我们采用分治算法divide-and-conquer策略。他的思想是将问题分成两个大致相等的子问题然后递归的对它们求解这是分的部分治的部分将两个子问题的解补充到一起并做少量的附加工作然后得到整个问题的解法。如上案例中我们最大子序列可能分布在三个地方 整个序列在输入数组的前半部分可以递归求解整个序列在输入数组的后半部分可以递归求解整个序列在输入数组的中间部分需要先求出前半部分的最大和其中包含最后一个元素在求后半部分最大和其中包含首个元素将两个和相加 我给出如下算法实现
/*** author liaojiamin* Date:Created in 16:38 2021/1/29*/
public class MaxSumRec {public static int[] getArrayData(int size) {int[] arrayData new int[size];Random random new Random();for (int i 0; i size; i) {int temp random.nextInt(50);if (temp 25) {arrayData[i] temp;} else {int value temp - 2 * temp;arrayData[i] value;}}return arrayData;}/*** 分治算法* */public static int getMaxSumRec_1(int[] arrayData){return getMaxSumRecDivide(arrayData, 0, arrayData.length -1);}public static int getMaxSumRecDivide(int[] arrayData, int left, int right){if(left right){return arrayData[left] 0 ? arrayData[left] : -1;}int center (left right)/2;int maxLeft getMaxSumRecDivide(arrayData, left, center);int maxRight getMaxSumRecDivide(arrayData, center 1, right);int maxLeftBordeSum 0;int leftBordeSum 0;for(int i center; i left; i--){leftBordeSumarrayData[i];if(maxLeftBordeSum leftBordeSum){maxLeftBordeSum leftBordeSum;}}int maxRightBordeSum 0;int rightBordeSum 0;for(int i center1; iright;i){rightBordeSumarrayData[i];if(maxRightBordeSum rightBordeSum){maxRightBordeSum rightBordeSum;}}return Math.max(Math.max(maxLeft, maxRight), maxLeftBordeSummaxRightBordeSum);}public static void main(String[] args) {int[] arraydata getArrayData(20);for (int i 0; i arraydata.length; i) {System.out.print(arraydata[i] , );}System.out.println();System.out.println(getMaxSumRec_1(arraydata));}
}如上算法的运行次数分析如下: 令T(N)是求解大小为N的最大子序列的问题所花费的世界。如果N1则只需要执行最基础情况环肥常数时间量1个单位时间得到T(1) 1如果N1则必须运行两个递归调用以及之后的循环和最后的最大值判断因为分治算法保证每个子问题不重叠那么我们在循环中必然是每个元素范文一次那么我们for循环总共解除到A_0~A_n-1 每一个元素因此花费O(N)时间毫无疑问接着看递归部分我们假设N是偶数那么两个递归的基数是一样的我们每次递归得到原来基数数据的一半那么每一个子递归总的花费时间是T(N/2)此处可以用数学归纳法证明N被无限二分达到基数为1 的次数此处略因此递归共花费2T(N/2)个时间单位如上总数花费时间2T(N/2) O(N)
T(1) 1
T(N) 2T(N/2) O(N)得到如上的数学公式为简化计算我们用N代替O(N)项由于T(N)最终还是要用大O表示因此这么做不影响答案此处我们只进行递推不进行数学证明依据以上公式T(N) 2T(N/2)N且T(1) 1那么我们得到 T(2) 2T(1) 2 4 22 T(4) 2T(2) 4 12 43 … T(16) 2T(8) 16 80 16*5若N2^k,则 T(N) N*(k1) N*LogN N O(NlogN)
最大子序列和投机方法
一个循环解决此问题如下实现
public static int getMaxSumRec_2(int[] arrayData){int maxSum 0, thisSum 0;for (int i 0; i arrayData.length; i) {thisSumarrayData[i];if(thisSum maxSum){maxSum thisSum;}else if (thisSum 0){//如果之前项累计不大于0 则情况之前项和从小计数thisSum 0;}}return maxSum;}再谈快排
快速排序是经典的分支算法应用我们在之前的排序归纳文章中已经给出过具体的算法分析以及实现基本算法都是如下几个步骤 如果S集合中元素个数是0或者1则返回取S中任何一个元素V称为枢纽元pivot将S-{V}S中其他元素划分为两个不想交的集合S1 { X \in S-{V} |XV | } 和 S2 { X \in S-{V} |XV | }返回{quickSort(S1)} 后跟v继续返回 quickSort(S2) 以上算法中针对枢纽元的选择上并没有详细处理因此这就成了一种设计决策一部分好的实现方法是将这种情形尽可能完美的解决。直观的看我们洗碗能将集合中的一半关键字分配到S1 中另外一半分配到S2很想二叉树。
枢纽元选择
虽然不管枢纽元选择的那个元素最终都能完成排序但是有些选择明显更优秀。错误的选择方式 我们之前的算法中直接选择的第一个元素作为枢纽元因为当时的算法说明中数据来源是随机生成数组成的数列那么这种情况是可以接受的。当时如果输入的数列是已有序的数列或者反序列那么这样的枢纽元选取会产生一个最差情况的分割因为所有的元素不是被分配到S1就是S2并且这种情况会发生在递归排序的所有调用中。时间复杂度O(N^2)另外一种方法是选取前两个互异的关键字中的较大者作为枢纽元不过这种值选取第一个元素作为枢纽元具有相同的问题 一种安全的做法 随机选择枢纽元一般来说这种策略非常安全除非随机数发生器有问题因为随机的枢纽元不可能总在接连不断的产生劣质的分割另一方面随机数的生成开销比较大根本减少不了算法其余部分的平均运行时间。三数中值分割法Median-of-Three Partitioning :一组N个数的中值是滴N/2 个最大的数。枢纽元最好的选择数是数组的中值。但是这很难算出并且明显减慢快排的速度这样的中值的估计量我们可以通过随机选取三个数并用他们的中值作为枢纽元而得到。而实际上随机性并没有这么大的帮助因此一般的做法是使用左端右端和中间位置的三个元素的中值作为枢纽元。
分割策略
有几种分割策略用于实践我们给出的分割策略已经被证明能够给出好的结果。我们将枢纽元与最后的元素交换使得枢纽元离开要被分割的数据段。i从第一个数据开始j从倒数第二个元素开始。我们用如下动图 上图用的交换法当i在j左边的时候我们将i右移移过哪些小于枢纽元的元素并且建j左移移过哪些大于枢纽元的元素当i和j停止时候i指向一个大元素j指向一个小元素。如果i在j左边那么将交换这两个元素。最后效果是将大元素推向右边小元素推向左边。最后如果i 到了j 的右边并且停在第一个最大的元素时候我们停止交换i j 并且将pivot与i 交换。在最后一个步骤当枢纽元与i 所指向的元素交换的时候我们知道在位置position i 的每一个元素都必须小于枢纽元类似position i 的元素都大于枢纽元。必须考虑的一个重要情况如何处理等于枢纽元情况i j 应该做相同的动作否则分割将会偏向一方。极端情况所有数据相等那么我们每次都需要交换虽然没有意义但是i j 将会在中间交错时间复杂度O(NlogN)实际情况几乎不会存在都相同情况所以我们让i j都停止并交换。
小数组
对于很小的数组N 20,快速排序不如插入排序快
快速排序实现
/*** author liaojiamin* Date:Created in 12:06 2021/2/1*/
public class DivideAndConquerGreat {public static void main(String[] args) {int[] beginArrayData getArrayData(30);System.out.println(------------------);int[] arrayData quickSort(beginArrayData);for (int i 0; i arrayData.length; i) {System.out.println(arrayData[i]);}}public static int[] quickSort(int[] arrayData) {if (arrayData null || arrayData.length 1) {return arrayData;}return quickSort(arrayData, 0, arrayData.length - 1);}public static int[] quickSort(int[] arrayData, int left, int right) {if(Math.abs(left - right) 20){insertionSort(arrayData, left, right);}else {if (left right) {int position swap(arrayData, left, right);quickSort(arrayData, left, position - 1);quickSort(arrayData, position 1, right);}}return arrayData;}/*** 快排主体实现*/public static int swap(int[] arrayData, int left, int right) {int position median3(arrayData, left, right);int i left ;int j right - 1;while (i j) {while (i j arrayData[i] position) {i;}while (i j arrayData[j] position) {j--;}if (i j) {swapElement(arrayData, i, j);}}//position初始位置是right-1swapElement(arrayData, i, right - 1);return i;}/*** 数据交换*/public static void swapElement(int[] arrayData, int i, int j) {int temp arrayData[i];arrayData[i] arrayData[j];arrayData[j] temp;}/*** 三数中值获取*/public static int median3(int[] arrayData, int left, int right) {int center (left right) / 2;if (arrayData[center] arrayData[left]) {swapElement(arrayData, center, left);}if (arrayData[right] arrayData[left]) {swapElement(arrayData, right, left);}if (arrayData[right] arrayData[center]) {swapElement(arrayData, right, center);}swapElement(arrayData, center, right - 1);return arrayData[right - 1];}/*** 插入排序*/public static int[] insertionSort(int[] arraydata, int left, int right) {if (arraydata null || arraydata.length 1) {return arraydata;}for (int i 0; i right; i) {for (int j i; j left; j--) {if (arraydata[j - 1] arraydata[j]) {int temp arraydata[j - 1];arraydata[j - 1] arraydata[j];arraydata[j] temp;}}}return arraydata;}/*** 随机生成数列*/public static int[] getArrayData(int size) {int[] arrayData new int[size];Random random new Random();for (int i 0; i size; i) {int temp random.nextInt(10);if (temp 0) {arrayData[i] temp;} else {int value temp - 2 * temp;arrayData[i] value;}System.out.println(arrayData[i]);}return arrayData;}
}上一篇数据结构与算法–贪婪算法2
