数据结构与算法学习笔记（四）

我不是女神ヾ 2023-09-29 10:48 128阅读 0赞

**目录**

一：递归

二：排序算法

三：平局时间复杂度和最坏时间复杂度

四：算法的空间复杂度

--------------------

## 一：递归 ##

**1.1 递归的概念：**

> 递归：就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**1.2 递归需要遵守的重要规则：**

>  *  执行一个方法时，就创建一个新的受保护的独立空间（栈空间）
>  *  方法的局部变量是独立的，不会相互影响，比如n变量
>  *  如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据
>  *  递归必须向退出递归的条件逼近，否则就是无限递归
>  *  当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

**案例1：迷宫**

package recursion;
    
    public class MiGong {
        public static void main(String[] args) {
            //先创建一个二维数组，模拟迷宫
            //地图
            int[][] map=new int[8][7];
            //使用数字‘1’表示墙
            for(int i=0;i<8;i++){
                for(int j=0;j<7;j++){
                    if(i==0||i==7||j==0||j==6){
                        map[i][j]=1;
                    }
                }
            }
            //设置挡板，用“1”表示
            map[2][2]=1;
            map[3][2]=1;
            map[4][2]=1;
            map[5][2]=1;
            map[6][3]=1;
    
                //原地图：
            System.out.println("原地图为：");
            for(int[] a:map){
                for(int i:a){
                    System.out.print(i+" ");
                }
                System.out.println();
            }
    
            //使用递归回溯给小球找路
            setWay(map,1,1);
    
            System.out.println("新的地图为：");
            //遍历二维数组,地图的情况
            for(int[] a:map){
                for(int i:a){
                    System.out.print(i+" ");
                }
                System.out.println();
            }
    
        }
        /*
        1.map表示地图
        2.i，j表示从地图的哪个位置开始出发（1，1）
        3.如果小球能到【6】【5】位置，则说明通路找到
        4.约定：当map【i】【j】为0表示该店没有走过，当为1表示墙；2表示通路可以走；3表示该点已经走过，但是走不通
        5.在走迷宫时，需要确定一个策略（方法）下-》右-》上-》左，如果该点走不通，再回溯
         */
        public static boolean setWay(int[][] map,int i,int j){
            if(map[6][5]==2){//通路已经找到,结束递归
                return true;
            }else {
                if(map[i][j]==0){//当前这个点还没有走过
                    //按照策略---下-》右-》上-》左
                    map[i][j]=2;//假定该点是可以走通
                    if(setWay(map,i+1,j)){//向下走
                        return true;
                    }else if(setWay(map,i,j+1)){//向右走
                        return true;
                    }else if(setWay(map,i-1,j)){//向上走
                        return true;
                    }else if(setWay(map,i,j-1)){//向左走
                        return true;
                    }else {
                        //说明该点是走不通的，是思路
                        map[i][j]=3;
                        return false;
                    }
                }else {//如果map【i】【j】！=0，可能是1，2，3
                    return false;
                }
            }
        }
    
    }

**案例2：八皇后问题：**

**![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_14_color_FFFFFF_t_70_g_se_x_16][]**

package recursion1;
    
    public class Queue8 {
        //定义一个max表示共有多少个皇后
        int max=8;
        //定义数组array，保存皇后放置位置的结果，比如arr={0,4,7,5,2,6,1,3}
        int[] array=new int[max];
        static int count=0;//一共有count种解法
        public static void main(String[] args) {
            Queue8 queue8=new Queue8();
            queue8.check(0);
            System.out.println("一共有"+count+"解法");
        }
        //写一个方法，可以将皇后拜访的位置输出
        private void print(){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        //查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
        /*
        n；表示第几个皇后
         */
        private boolean judge(int n){
            for(int i=0;i<n;i++){
                /*
                1. array[i]==array[n]:表示判断第n个皇后是否和前面的第n-1个皇后在同一列
                2. Math.abs(n-i)==Math.abs(array[n]-array[i]：表示判断第n个皇后是否和第i个皇后是否在同一斜线
                 */
                if(array[i]==array[n]||(Math.abs(n-i)==Math.abs(array[n]-array[i]))){
                    return false;
                }
            }
            return true;
        }
        //编写一个方法，放置第n个皇后
        //特别注意：check是每一次递归时，进入到check中都有for(int i=0;i<max;i++),因此会有回溯
        private void check(int n){
            if(n==max){//n==8,其实8个皇后就已经放好
                print();
                count++;
                return;
            }
            //依次放入皇后，并判断是否冲突
            for(int i=0;i<max;i++){
                //先把当前这个皇后n，放到该行的第1列
                array[n]=i;
                //判断当防止第n个皇后到i列时，是否冲突
                if(judge(n)){//不冲突
                    //接着放n+1个皇后，即开始递归
                    check(n+1);
                }
                //如果冲突，就继续执行array【n】=i，即将第n个皇后，防止在本行的后移的一个位置
            }
        }
    }

--------------------

## 二：排序算法 ##

**2.1 排序算法的定义：**

排序也称排序算法，排序是将一组数据，依指定的顺序进行排列的过程。

排序的分类：

> （1）内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。
> 
> （2）外部排序法：数据量过大，无法全部加载到内存中，需要借助外部内存进行排序。

（3）常见的排序算法分类：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_6_color_FFFFFF_t_70_g_se_x_16][]

**2.2 算法的时间复杂度：**

度量一个程序（算法）执行时间的两种方法：

> （1）事后统计的方法：这种方法可行，但是有两个问题，一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快。
> 
> （2）事前估算的方法：通过分析某个算法的时间复杂度来判断哪个算法更优。

**2.3 时间频度：**

时间频度的基本介绍：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_10_color_FFFFFF_t_70_g_se_x_16][]

**2.3.1 忽略常数项：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_17_color_FFFFFF_t_70_g_se_x_16][]

> **结论：**
> 
> （1）2n+20和2n随着n变大，执行曲线无线接近，20可以忽略。
> 
> （2）3n+10和3n随着n变大，执行曲线无线接近，10可以忽略。

**2.3.2 忽略低次项：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

>  **结论：**
> 
> （1）2n^2+2n+10和2n^2随着n变大，执行曲线无线接近，可以忽略3n+10
> 
> （2）n^2+5n+20和n^2随着n变大，执行曲线无线接近，可以忽略5n+20

**2.3.3 忽略系数：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_13_color_FFFFFF_t_70_g_se_x_16][]

>  **结论：**
> 
> （1）随着n值变大，5n^2+7n和3n^2+2n,执行曲线重合，说明这种情况下，5和3可以忽略。
> 
> （2）二n^3+5n和6n^3+4n，执行曲线分离，说明多少次方是关键

**2.4 时间复杂度：**

（1）一般情况下，算法中的基本操作语句的重复执行次数时问题规模n的某个函数，用T（n）表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n）），成O（f（n））为算法的渐进时间复杂度，简称时间复杂度。

（2）T（n）不同，但时间复杂度可能相同。如T（n）=n^2+7n+6与T（n）=3n^2+2n+2，它们的T（n）不同，但时间复杂度相同，都为O（n^2）

（3）计算时间复杂度的方法：

>  *  用常数1代替运行时间中的所有加法常数
>  *  修改后的运行次数函数中，只保留最高阶项
>  *  去除最高阶项的系数

**2.5 常见的时间复杂度：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_10_color_FFFFFF_t_70_g_se_x_16 1][]

说明：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_11_color_FFFFFF_t_70_g_se_x_16][]

**2.5.1 常数阶O（1）：**

> 无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O（1）

int i=1;
    int j=2;
    ++i;
    j++;
    int m=i+j;

> 说明：
> 
> 上述代码在执行的时候，它小号的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O（1）来表示它的时间复杂度。

**2.5.2 对数阶O（log2n）：**

int i=1;
    while(i<n){
    i=i*2;
    }

> 说明：
> 
> 在while循环里面，每次都将i乘以2，乘完之后，i距离n就越来越近了。假设循环x次之后，i就大于2了，此时这个循环就退出了，也就是说2的x次方等于n，那么x=log2n，也就是说当循环log2n次以后，这个代码就结束了。因此这个代码的时间复杂度为：O（log2n）。O（log2n）的这个2实际上是根据代码变化的，i=i\*3，则是O（log3n）

**2.5.3 线性阶O（n）：**

for(int i=1;i<=n;i++){
    
    j=i;
    j++;
    }

> 说明：
> 
> 这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O（n）来表示它的时间复杂度。

**2.5.4 线性对数阶O（nlogN）：**

for(m=1;m<n;m++){
    i=1;
    while(i<n){
    i=i*2;
    }
    }

> 说明：
> 
> 线性对数阶O（nlogN）就是将时间复杂度为O（logn）的代码循环N遍

**2.5.5 平方阶O（n^2）:**

for(int x=1;x<n;x++){
    for(int i=1;i<n;i++){
    j=1
    j++;
    }
    
    
    }

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_11_color_FFFFFF_t_70_g_se_x_16 1][]

--------------------

## 三：平局时间复杂度和最坏时间复杂度 ##

> （1）平均时间复杂度是值所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
> 
> （2）最坏情况下的时间复杂度成最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
> 
> （3）平均时间复杂度和最坏时间复杂度是否一致，与算法有关。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_6_color_FFFFFF_t_70_g_se_x_16 1][]

--------------------

## 四：算法的空间复杂度 ##

> 1.  类似于时间辅助度的讨论，一个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模n的函数。
> 2.  空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
> 3.  **在做算法分析时，主要讨论的是时间复杂度。**从用户使用体验上看，更看重的程序执行的速度。一些缓存产品和算法（基数排序）本质就是用空间换时间。

--------------------

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d29812e1c0234de29ac13e23018d1a8f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_14_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3d62b96436db4037a55e5c6a85d5bf0d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_14,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_6_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3791855bb7ba4dd59c482d8043d7b6c9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_6,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_10_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/e1f63644e2a84a9182f45d420c910308.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_10,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7cf574565dcf4772af35d4c1172cebc1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_14_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/5dd64b1c077942129c40caeb5cf46b9b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_14,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/00b0d9dfff0245abbbfb4d2888f09894.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_10_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/a9986fb8dada417981a1c79d222fd664.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_10,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/78fed33e1b934d8e970b7505e6aca8c6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/9d25bcdc053f41e4a9236e42819710c9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ_size_6_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/57405915dac447f9946bbfd31510def3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmlhWGluZ05hc2hpc2h1YQ==,size_6,color_FFFFFF,t_70,g_se,x_16