算法思维：⼆分思想,舍弃思想,递归树思想前⾔思想:⼆分思想,舍弃思想,递归树思想,重点:数轴,树思想,栈思想,⼆分,多分思想,master公式⼀遇递归,直接造树!!递归,永远不要把它当作⼀个⽅法,你可以把它当作⼀个过程树先想想递归最⼤值:1.[L,R]上求最⼤值定:递归求最⼤,数轴,拆分为树解:1.⼆分思想,两个跑肯定⽐单个跑快--那么就涉及到中间,中间数的求法最好就是舍弃法2.中间为分界,左边跑,右边跑3.调⽤Math函数进⾏⽐较思维解:1.多叉树,2.利⽤栈后继遍历.3.悬⽽未决压⼊栈4.清晰的就出去5.⾼度上压栈悬⽽未决(有的孩⼦(⼦节点)不知道是多少)栈弹出,遇到我们的判断出递归条件规范:只有⼀个数?直接处理注:Math虽然好⽤,但只能⽤于判断回值.数据的交换,还是需交换⽅式,舍弃法(关于舍弃,很⼤的表现就是有效增益--可看⼒扣53.最⼤⼦序和)求最⼤使⽤树的⽅式,将我们要求的因⼦找出来,减少普通排序的⼀次次⽐较2.递归的master公式---(重点)定:递归的复杂度,递归的执⾏流程解:1.先树,栈的形式解析整个递归 ---发现树的⾼度就是递归的次数2.master公式的学习T(N)=a*(N/b)+O(N^d)主⽅法 = 次数*⼦⽅法+其它 --- 递归的主⽅法和⼦⽅法也就参数不⼀样a指的是调⽤⽅法次数,b指的是切割问题⼏段,,N指的是复杂度3.时间复杂度的计算1.log(b,a)>d--->复杂度O(N^log(b,a))2.log(b,a)复杂度O(N^d)3.log(b,a)==d--->复杂度O(O^d * logN)⼀般使⽤递归是为了职责分明,递归就进栈,弹栈就好了,弹栈是由⾃⼰写的条件控制.有多⼦递归时,那就树来⾛归并本质:⼆分排序,再合并归并的做法是:左侧⽐较完,右侧⽐较完,再最后左右⽐较还是两两交换,,不管是for循环,还是递归---两者都是使⽤⼆分思想来变成O(logN),本质是让两个数两两交互排序归并递归法我测试了它的递归⾛向发现它的⾛向是按照(终⽌条件,⽅法体控制的),递归的本质是都⾛怎么⾛,就是如果⾥⾯是双⼦递归,那么它会按树⾛,⾛的时候,是先左⼤节点,再左⼤节点的左⼦节点,再左⼤节点的右⼦节点.(往复进⾏),中途⾛到终⽌条件跳出,其它继续执⾏,,遇到很⼩的满⾜要求⽅法体的也会去执⾏.它的⽬的就是,整个流程我都整出来并且压⼊栈,执⾏完的或者遇到条件的就出去,按照你的控制停⽌,你有条件,满⾜就执⾏.必须明⽩的递归弹栈数组为{11,8,9,4,12,3,7,6}--[0,7]开始,进栈[0,7],遇到⼦,再进栈[0,3],遇到⼦,再进栈[0,1],再遇到再进,直到遇到该停⽌的,再不断的弹,弹出这⼀步,⾛下⼀步,下⼀步再弹,再...简单没有弹,只是顺序执⾏的流程这是⼀个,没有终⽌弹栈的流程原数据:11,8,9,4,12,3,7,6递归流程:0--1⽅法执⾏:8 11递归流程:2--3⽅法执⾏:4 9递归流程:0--3⽅法执⾏:4 8 9 11递归流程:4--5⽅法执⾏:3 12递归流程:6--7⽅法执⾏:6 7递归流程:4--7⽅法执⾏:3 6 7 12递归流程:0--7⽅法执⾏:3 4 6 7 8 9 11 12输出结果:3 4 6 7 8 9 11 12归并排序代码:public class MergeSortTest {// 解---由⼤到⼩解决,// 1.解递归// 0,R都是数组下标public void process(int arr[],int L,int R){if(L==R){ // 结束标志,也就是叶⼦节点结束return;}int m = L+((R-L)>>1);process(arr,L,m); //----L----m-----R-- 不仅仅⼀个,是树process(arr,m+1,R);/* System.out.println("递归流程"+":"+L + "--" + R);*/merge(arr,L,m,R);}// 2.解排序--按照最基本的叶⼦进⾏计算,满⾜最基本的LMR的叶⼦进⾏思考,如 529public void merge(int arr[],int L,int M,int R){// 定:要使得两边有序 ---// 解:最基本的叶⼦,529---// 需求:指针,[L,M]边的,[M,R]边的int p1 = L;int p2 = M+1;// 辅助数组存值int help[] = new int[R-L+1];int i = 0; // 辅助的指针// 节点卡标while (p1 <= M && p2 <= R){ // 有⼀个指针满⾜就停⽌help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; // 此时必定会将⼀边的全打进去}while (p1 <= M){help[i++] = arr[p1++];}while (p2 <= R){help[i++] = arr[p2++];}for (int j = 0; j < help.length; j++) {arr[L+j] = help[j];}/*// merge⽅法体流程!System.out.print("⽅法执⾏:");for (int i1 : help) {System.out.print(i1+" ");}System.out.println();*/}public static void main(String[] args) {MergeSortTest mergeSortTest = new MergeSortTest();int arr[] = new int[]{11,8,9,4,12,3,7,6};System.out.println("原数据:"+ "11,8,9,4,12,3,7,6");mergeSortTest.process(arr,0,arr.length-1);System.out.print("输出结果:");for (int i : arr) {System.out.print(i+" ");}}}BS:本⼈⽬前也是在算法的路上不断探索中,试图和数据结构以及⼏何进⾏挂钩的学习,没有图形的算法是没有灵魂的!⽂章中可能有很多不对的地⽅,希望能多多指教,评论;博主在此感谢!。
