一剖析递归行为和递归行为时间复杂度的估算用递归方法找一个数组中的最大值系统上到底是怎么做的master 公式的使用T(N) a*T(N/b) O(N^d)1log(b,a) d - 复杂度为 O(N^log(b,a))2log(b,a) d - 复杂度为 O(N^d * logN)3log(b,a) d - 复杂度为 O(N^d)补充阅读www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html1.递归实现找一个数组中的最大值说明求中点的位置一般来说是mid(LR)/2但是如果数组开的长度过大对LR计算时会产生溢出故可以写成midL(R-L)/2,采用右移可以写成midL(R-L)1。代码package class002; import java.util.Arrays; //递归方法实现求数组最大值 public class Code_GetMax { public static int getMax(int[] arr){ return process(arr,0,arr.length-1); } //arr[L..R]范围上求最大值 N public static int process(int[]arr,int L,int R){ if (LR){//arr[L..R]范围上只有一个数直接返回basecase return arr[L]; } // for (int iL;iR;i){ // System.out.println(arr[i]); // } int midL((R-L)1);//中点 int leftMaxprocess(arr,L,mid); int rightMaxprocess(arr,mid1,R); return Math.max(leftMax,rightMax); } public static void main(String[] args){ int []arr1{1,2,3,4}; int []arr2{11,43,32,12,24}; System.out.println(arr1 Arrays.toString(arr1)); System.out.println(arr1 max: getMax(arr1)); System.out.println(arr2 Arrays.toString(arr2)); System.out.println(arr2 max: getMax(arr2)); } }运行结果arr1[1, 2, 3, 4] arr1 max: 4 arr2[11, 43, 32, 12, 24] arr2 max: 43解释对于数组【325674】对应序列{012345}开始:1p(0,5)-p(0,2)p(3,5)2p(0,2)-p0,1)p(2,2),此时p(2,2)return;p(3,5)-p(3,4)p(5,5),此时p(5,5)return;3p(0,1)-p0,0)p(1,1),此时p(0,0)return,p(1,1)return;p(3,4)-p(3,3)p(4,4),此时p(3,3)return,p(4,4)return;结束。类似于后序遍历后序遍历(PostOrder) 的操作过程如下若二叉树为空则什么也不做否则1)后序遍历左子树;2)后序遍历右子树;3)访问根结点。流程图[0~5] / \ [0~2] [3~5] / \ / \ [0~1] [2] [3~4] [5] / \ 5 / \ 4 [0] [1] [3] [4] 3 2 6 72.master 公式的使用T(N) a*T(N/b) O(N^d)其中TN是母问题的规模每个大小为N,T(N/b)是子问题的规模每个大小为N/ba是调用次数O(N^d)是除去调用之外剩下的过程d 0当前层只做常数次操作比如加减比较大小d 1当前层需要遍历 N 个数据比如循环打印数组。简单说就是一个问题N个数据拆分成a个小问题每个小问题有N/b个数据。对于1中的问题不循环打印一遍数组a2b2,d0,T(N) 2*T(N/2) O(1)如果循环打印一遍数组就变成a2b2,d1,T(N) 2*T(N/2) O(N)。1log(b,a) d - 复杂度为 O(N^log(b,a))2log(b,a) d - 复杂度为 O(N^d * logN)3log(b,a) d - 复杂度为 O(N^d)对于1中的问题不循环打印一遍数组a2b2,d0,T(N) 2*T(N/2) O(1)时间复杂度为O(N^log(2,2))ON如果循环打印一遍数组就变成a2b2,d1,T(N) 2*T(N/2) O(N),时间复杂度为ON*logN。二归并排序1整体就是一个简单递归左边排好序、右边排好序让其整体有序2让其整体有序的过程里用了外排序方法3利用master公式来求解时间复杂度4归并排序的实质由master公式可知归并排序的时间复杂度 O(N*logN)额外空间复杂度 O(N)1.时间复杂度归并排序与选择排序的区别选择排序每次只比较一个元素的信息只有一个元素有序没有把比较的信息传递下来因此算法复杂度是O(n^2);归并排序通过将元素划分到单一元素在最小的单元上进行比较形成了局部有序的单元在单元合并的时候把比较的信息传递下来因此时间复杂度为O(N*NlogN)。2.空间复杂度申请了一个外部数组用完即释放(Java特性C需要手动释放注意区别)因此空间复杂度为O(N)3.代码package class002; import java.util.Arrays; public class Code_MergeSort { public static void mergeSort(int[] arr){ if (arr null || arr.length2){ return; } process(arr,0,arr.length-1); } public static void process(int[] arr,int L,int R){ if(LR){ return; } int midL((R-L)1); process(arr,L,mid); process(arr,mid1,R); merge(arr,L,mid,R); } public static void merge(int[] arr,int L,int M,int R){ int[] helpnew int[R-L1];//开辟辅助空间等于数组大小 int i0; int p1L;//左侧区域从L开始 int p2M1;//右侧区域从M1开始 while(p1M p2R){ //不越界的情况下如果p1位置的数小于p2位置的数将p1位置的数拷贝到help[i]位置上去且p1向右移动一位i的位置也右移 //如果p1位置的数不小于p2位置的数将p2位置的数拷贝到help[i]位置上去且p2向右移动一位i的位置也右移 //直到发生越界 help[i]arr[p1]arr[p2] ? arr[p1]:arr[p2]; } //如果越界则会执行下面两个while循环中的其中一个谁没越界则把剩下的数拷贝到help[i]中去 while (p1M){ help[i]arr[p1]; } while(p2R){ help[i]arr[p2]; } //最后把整个数组拷贝回arr[]中完成整个过程 for (i0;ihelp.length;i){ arr[Li]help[i]; } } public static void main(String[] args){ int []arr1{4,8,9,43,21}; int []arr2{11,43,32,12,24}; System.out.println(arr1 Arrays.toString(arr1)); mergeSort(arr1); System.out.println(arr1 mergeSort: Arrays.toString(arr1)); System.out.println(arr2 Arrays.toString(arr2)); mergeSort(arr2); System.out.println(arr2 mergeSort: Arrays.toString(arr2)); } }运行结果arr1[4, 8, 9, 43, 21] arr1 mergeSort: [4, 8, 9, 21, 43] arr2[11, 43, 32, 12, 24] arr2 mergeSort: [11, 12, 24, 32, 43]执行过程[4,8,9,43,21] //拆分 [4,8,9,43,21] / \ [4,8,9] [43,21] / \ / \ [4,8] [9] [43] [21] / \ [4] [8] //合并同时排序 [4] [8] ↓ [4,8] [4,8] [9] ↓ [4,8,9] [43] [21] ↓ [21,43] [4,8,9] [21,43] ↓ [4,8,9,21,43]4.归并排序的扩展小和问题和逆序对问题小和问题在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和。求一个数组的小和。例子[1, 3, 4, 2, 5]1左边比1小的数没有3左边比3小的数14左边比4小的数1、32左边比2小的数15左边比5小的数1、3、4、2所以小和为1131134216逆序对问题在一个数组中左边的数如果比右边的数大则这两个数构成一个逆序对请打印所有逆序对。1小和问题分析求小和的过程实际上是这个数组中的每个数在问题中会被加几次可以反过来比较每一个数的右边有几个数比这个数大。举例[1, 3, 4, 2, 5]1右边边比1大的数4个4*143右边比3大的数2个2*364右边比4大的数1个1*442右边比2大的数1个1*225右边比5大的数没有所以小和为464216等效于原来的例子。gpt的“矩阵”解释因此可以采用归并排序但与归并排序的一点差别是面对左组和右组相等的情况一定要先拷贝右组。代码package class002; import java.util.Arrays; public class Code_SmallSum { public static int smallSum(int[] arr){ if (arrnull|| arr.length2){ return 0; } return process(arr,0,arr.length-1); } //arr[L..R]既要排好序也要求小和 public static int process(int[] arr,int l,int r){ if(lr){ return 0; } int midl((r-l)1); //返回左侧排序并求小和的数量右侧排序并求小和的数量左右侧都排好时小和的数量 return process(arr,l,mid) process(arr,mid1,r) merge(arr,l,mid,r); } public static int merge(int[]arr,int L,int m,int r){ int[] helpnew int[r-L1]; int i0; int p1L; int p2m1; int res0; while (p1m p2r){ //都不越界时只有左组比右组小才产生小和数量增加的情况 //添加的小和量当前右组的数有多少个比当前p1所指的数大*p1的值 //如果左组不比右组小小和增加的量0 resarr[p1]arr[p2]?(r-p21)*arr[p1]:0; //拷贝如果左组严格比右组小的时候才拷贝左组大于等于的时候拷贝右组 help[i]arr[p1]arr[p2]?arr[p1]:arr[p2]; } //越界情况不产生小和 while(p1m){ help[i]arr[p1]; } while(p2r){ help[i]arr[p2]; } for(i0;ihelp.length;i){ arr[Li]help[i]; } return res; } public static void main(String[] args){ int []arr1{4,8,9,43,21}; int []arr2{11,43,32,12,24,12}; System.out.println(arr1 Arrays.toString(arr1)); System.out.println(arr1 smallSum: smallSum(arr1)); System.out.println(arr2 Arrays.toString(arr2)); System.out.println(arr2 smallSum: smallSum(arr2)); } }运行结果arr1[4, 8, 9, 43, 21] arr1 smallSum: 58 arr2[11, 43, 32, 12, 24, 12] arr2 smallSum: 67相关题目leetcode3152逆序对分析逆序对问题本质上是在统计数组中所有满足下面条件的数对ij,arr[i]arr[j]也就是左边的数比右边的数大这两个数就构成一个逆序对。例如数组[3, 1, 4, 2, 5]逆序对有(3,1) (3,2) (4,2)所以一共有 3 个逆序对。如果暴力做就是对每个数都检查它右边所有的数时间复杂度是O(N2)O(N^2)用归并排序可以优化。归并时左右两部分已经有序。假设左[3,7,9] 右[2,8]当前比较3 2因为左边已经有序3 7 9所以既然3 2那么一定有7 2 9 2因此可以一次确定(3,2) (7,2) (9,2)逆序对数量就是m-p11所以归并排序解决逆序对的核心就是if (arr[p1] arr[p2]) { // arr[p1...m] 都和 arr[p2] 构成逆序对 }整体可以理解为总逆序对左半部分逆序对右半部分逆序对跨左右两部分的逆序对只统计数量时时间复杂度是O(Nlog⁡N)如果题目要求“打印所有逆序对”最坏情况下逆序对本身就有O(N^2) 个因此输出时间最坏也会达到O(N^2)。代码package class002; import java.util.Arrays; public class Code_ReversePair { //打印数组中所有的逆序对并返回逆序对数量 public static int reversePair(int[] arr){ if (arrnull || arr.length2){ return 0; } return process(arr,0,arr.length-1); } //arr[L...R] //1.要排好序 //2.要找到并打印其中所有逆序对 //3.返回逆序对数量 public static int process(int[] arr,int L,int R){ if(LR){ return 0; } int midL((R-L)1); //总逆序对 //左边内部逆序对 //右边内部逆序对 //左右两组之间产生的逆序对 return process(arr,L,mid) process(arr,mid1,R) merge(arr,L,mid,R); } public static int merge(int[]arr,int L,int m,int R){ int[]helpnew int[R-L1]; int i0; int p1L;//左组指针 int p2m1;//右组指针 int res0; while(p1m p2R){ /* * 如果 * * arr[p1] arr[p2] * * 因为左边已经有序 * * arr[p1] arr[p11] ... arr[m] * * 所以 * * arr[p1] * arr[p11] * ... * arr[m] * * 全部都比 arr[p2] 大。 * * 因此产生 * * m - p1 1 * * 个逆序对。 */ if (arr[p1]arr[p2]){ //打印这一批逆序对 for (int jp1;jm;j){ System.out.println( (arr[j],arr[p2]) ); } //增加逆序对数量 resm-p11; //右边的数比较小放入help help[i]arr[p2]; }else { /* * arr[p1] arr[p2] * * 不构成逆序对。 * * 注意 * 相等也不能算逆序对 * 因为题目要求严格 */ help[i]arr[p1]; } } //左组还有剩余 while(p1m){ help[i]arr[p1]; } //右组还有剩余 while(p2R){ help[i]arr[p2]; } //把排序后的结果复制回原数组 for(i0;ihelp.length;i){ arr[Li]help[i]; } return res; } public static void main(String [] args){ int []arr{3,3,4,2,5,63,44}; System.out.println(原数组); System.out.println(Arrays.toString(arr)); System.out.println(逆序对); int countreversePair(arr); System.out.println(逆序对数量count); System.out.println(排序后的数组 Arrays.toString(arr)); } }运行结果原数组 [3, 3, 4, 2, 5, 63, 44] 逆序对 (4,2) (3,2) (3,2) (63,44) 逆序对数量4 排序后的数组[2, 3, 3, 4, 5, 44, 63]三荷兰国旗问题与快速排序1.荷兰国旗问题问题一给定一个数组arr和一个数num请把小于等于num的数放在数组的左边大于num的数放在数组的右边。要求额外空间复杂度O(1)时间复杂度O(N)问题二荷兰国旗问题/leetcode75给定一个数组arr和一个数num请把小于num的数放在数组的左边等于num的数放在数组的中间大于num的数放在数组的右边。要求额外空间复杂度O(1)时间复杂度O(N)问题一分析1[i]num,将[i]和区的下一个数交换,区向右扩一个位置i;2[i]num,i;问题二分析这里相对于问题一多了一个区域边界。假定数组长度为N范围[0~N-1]先设定两个初始区域区域和区域初始大小为0位于数组的两端起始位置接着设置一个“等于比较器k”在数组中不断向右移动1“等于比较器k”遇到第一个比自己小的数则“区”向右增加1“等于比较器k”遇到第一个比自己小的数则“区”向右增加1范围变为[0~0]“等于比较器k”向右移动一位2“等于比较器k”遇到和自己相等的数则直接向右移动3等于比较器k”遇到第一个比自己大的数则将它和数组末端[N-1]进行交换注意由于[N-1]只是被交换而没有被检查所以i必须不动“区”向左扩一位范围变成[N-1~N-1]——此时用等于比较器k”检查这个被交换过来的数如果这个被交换过来的数大于等于比较器k那么这个被交换过来的数向左移动重复1的操作否则重复2的操作否则重复3的操作。当“区”和“等于比较器k”装上时流程终止。程序流程1[i]num,[i]和区下一个交换区右扩i;2[i]num,i;3[i]num,[i]和区前一个交换区左扩i原地不变。问题一代码package class002; import java.util.Arrays; public class Code_Partition { // 问题一 // num 的数放左边 // num 的数放右边 public static void partition(int[] arr, int num) { if (arr null || arr.length 2) { return; } // 区的右边界 int lessEqual -1; // 当前检查的位置 int i 0; while (i arr.length) { if (arr[i] num) { // 区向右扩大一个位置 // 当前数和区的新位置交换 swap(arr, lessEqual, i); } // 无论当前数 num 还是 num // i都向右移动 i; } } public static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {7, 3, 5, 2, 8, 5, 1, 9}; int num 5; System.out.println(原数组); System.out.println(Arrays.toString(arr)); partition(arr, num); System.out.println(调整后); System.out.println(Arrays.toString(arr)); } }运行结果原数组 [7, 3, 5, 2, 8, 5, 1, 9] 调整后 [3, 5, 2, 5, 1, 7, 8, 9]问题二代码package class002; import java.util.Arrays; public class Code_NetherlandsFlag { // 问题二 // num 放左边 // num 放中间 // num 放右边 public static void netherlandsFlag(int[] arr, int num) { if (arr null || arr.length 2) { return; } // 区的右边界 int less -1; // 区的左边界 int more arr.length; // 当前检查位置 int i 0; while (i more) { // 情况1当前数 num if (arr[i] num) { // 区右扩 // 当前数和区下一个位置交换 swap(arr, less, i); } // 情况2当前数 num else if (arr[i] num) { // 当前数已经属于区 // 直接向右移动 i; } // 情况3当前数 num else { // 区向左扩 // 当前数和区前一个位置交换 swap(arr, i, --more); // 注意 // i不能 // // 因为从右边交换过来的数 // 还没有检查过 } } } public static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } public static void main(String[] args) { int[] arr {7, 3, 5, 2, 8, 5, 1, 9, 5}; int num 5; System.out.println(原数组); System.out.println(Arrays.toString(arr)); netherlandsFlag(arr, num); System.out.println(调整后); System.out.println(Arrays.toString(arr)); } }运行结果原数组 [7, 3, 5, 2, 8, 5, 1, 9, 5] 调整后 [3, 2, 1, 5, 5, 5, 9, 8, 7]2.三类快速排序快速排序1.0版本最好时间复杂度O(N*logN),最差时间复杂度O(N^2),空间复杂度O(logN)。快速排序2.0版本荷兰国旗问题最好时间复杂度O(N*logN)时间复杂度O(N^2)原因(1)两者每次只能解决一个数的位置问题不能把位置信息进行传递;(2)划分在中间值附近时子问题规模相同可以用master公式划分在偏向两边时子问题规模不同不能用这个公式。快速排序3.0版本随机抽取一个数进行划分平均时间复杂度O(N*logN)证明略算法导论上有。4.2.1不改进的快速排序1把数组范围中的最后一个数作为划分值然后把数组通过荷兰国旗问题分成三个部分左侧 划分值中间 划分值右侧 划分值2对左侧范围和右侧范围递归执行分析1划分值越靠近两侧复杂度越高划分值越靠近中间复杂度越低2可以轻而易举地举出最差的例子所以不改进的快速排序时间复杂度为 O(N^2)4.2.2随机快速排序改进的快速排序1在数组范围中等概率随机选一个数作为划分值然后把数组通过荷兰国旗问题分成三个部分左侧 划分值中间 划分值右侧 划分值2对左侧范围和右侧范围递归执行3时间复杂度为 O(N*logN)代码package class002; import java.util.Arrays; public class Code02_QuickSort { public static int[] sortArray(int[] nums) { if (nums.length 1) { quickSort2(nums, 0, nums.length - 1); } return nums; } // 随机快速排序经典版(不推荐) public static void quickSort1(int[] arr, int l, int r) { if (l r) { return; } // 随机这一下常数时间比较大 // 但只有这一下随机才能在概率上把快速排序的时间复杂度收敛到O(n * logn) int x arr[l (int) (Math.random() * (r - l 1))]; int mid partition1(arr, l, r, x); quickSort1(arr, l, mid - 1); quickSort1(arr, mid 1, r); } // 已知arr[l....r]范围上一定有x这个值 // 划分数组 x放左边x放右边并且确保划分完成后x区域的最后一个数字是x public static int partition1(int[] arr, int l, int r, int x) { // a : arr[l....a-1]范围是x的区域 // xi : 记录在x的区域上任何一个x的位置哪一个都可以 int a l, xi 0; for (int i l; i r; i) { if (arr[i] x) { swap(arr, a, i); if (arr[a] x) { xi a; } a; } } swap(arr, xi, a - 1); return a - 1; } public static void swap(int[] arr, int i, int j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } // 随机快速排序改进版(推荐) public static void quickSort2(int[] arr, int l, int r) { if (l r) { return; } // 随机这一下常数时间比较大 // 但只有这一下随机才能在概率上把快速排序的时间复杂度收敛到O(n * logn) int x arr[l (int) (Math.random() * (r - l 1))]; partition2(arr, l, r, x); // 为了防止底层的递归过程覆盖全局变量 // 这里用临时变量记录first、last int left first; int right last; quickSort2(arr, l, left - 1); quickSort2(arr, right 1, r); } // 荷兰国旗问题 public static int first, last; // 已知arr[l....r]范围上一定有x这个值 // 划分数组 x放左边x放中间x放右边 // 把全局变量first, last更新成x区域的左右边界 public static void partition2(int[] arr, int l, int r, int x) { first l; last r; int i l; while (i last) { if (arr[i] x) { i; } else if (arr[i] x) { swap(arr, first, i); } else { swap(arr, i, last--); } } } public static void main(String[] args) { // 测试 quickSort1经典版 System.out.println( 测试 quickSort1 ); int[] arr1 {5, 3, 8, 4, 2, 7, 1, 6}; System.out.println(排序前: Arrays.toString(arr1)); Code02_QuickSort.quickSort1(arr1, 0, arr1.length - 1); System.out.println(排序后: Arrays.toString(arr1)); // 测试 quickSort2改进版 System.out.println(\n 测试 quickSort2 ); int[] arr2 {9, 2, 7, 2, 5, 2, 8, 1}; System.out.println(排序前: Arrays.toString(arr2)); Code02_QuickSort.quickSort2(arr2, 0, arr2.length - 1); System.out.println(排序后: Arrays.toString(arr2)); } }运行结果 测试 quickSort1 排序前: [5, 3, 8, 4, 2, 7, 1, 6] 排序后: [1, 2, 3, 4, 5, 6, 7, 8] 测试 quickSort2 排序前: [9, 2, 7, 2, 5, 2, 8, 1] 排序后: [1, 2, 2, 2, 5, 7, 8, 9]