前言

  • 思想:二分思想,舍弃思想,递归树思想,
  • 重点:数轴,树思想,栈思想,二分,多分思想,master公式
  • 一遇递归,直接造树!!
  • 递归,永远不要把它当作一个方法,你可以把它当作一个过程树

先想想递归最大值:

  • 1.[L,R]上求最大值

    • 定:递归求最大,数轴,拆分为树
    • 解:
      • 1.二分思想,两个跑肯定比单个跑快--那么就涉及到中间,中间数的求法最好就是舍弃法
      • 2.中间为分界,左边跑,右边跑
      • 3.调用Math函数进行比较
      • 思维解:
        • 1.多叉树,2.利用栈后继遍历.3.悬而未决压入栈 4.清晰的就出去 5.高度上压栈
          • 悬而未决(有的孩子(子节点)不知道是多少)
          • 栈弹出,遇到我们的判断出递归条件
    • 规范:只有一个数?直接处理
    • 注:Math虽然好用,但只能用于判断回值.数据的交换,还是需交换方式,
  • 舍弃法(关于舍弃,很大的表现就是有效增益--可看力扣53.最大子序和)
    算法思维:二分思想,舍弃思想,递归树思想-LMLPHP

  • 求最大
    算法思维:二分思想,舍弃思想,递归树思想-LMLPHP

  • 使用树的方式,将我们要求的因子找出来,减少普通排序的一次次比较

  • 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)
        • 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的叶子进行思考,如 529
    
    
            public 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:

  • 本人目前也是在算法的路上不断探索中,试图和数据结构以及几何进行挂钩的学习,没有图形的算法是没有灵魂的!
  • 文章中可能有很多不对的地方,希望能多多指教,评论;博主在此感谢!
10-07 21:14