数据结构与算法|第1节

桃扇骨 2023-10-01 20:53 135阅读 0赞

#### 文章目录 ####

*  前言
 *  一、数据结构
 *   *  1. 什么是数据结构
 *  二、算法
 *   *  1. 什么是算法
     *  2. 什么是好的算法
     *  3. 复杂度分析
     *   *  1. 常数时间
         *  2. 线性时间
         *  3. 对数时间
         *  4. 次方时间
         *  5. 指数时间
         *  6. 阶乘时间
     *  4. 常见复杂度比较

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

## 前言 ##

为什么要学习数据结构与算法？  
对于大部分的业务开发者来说，平常我们基本上都是利用现成已经封装好的接口，或者类库，加上一堆的业务逻辑来实现需求功能，很少会注意到数据结构与算法，比如说你用一个类库，你不懂得时间、空间复杂度的分析就不能感受到它的巧妙，写业务逻辑时什么时候用 AarryList 什么时候用 LinkedList，怎么让代码变得更加高效，为什么哪些很牛逼的框架能在高并发的情况下还能保持如此高的效率？学习数据结构和算法其实就是为了能够让我们有目的性的建立时间和空间复杂度，写出高质量的代码，能够设计基础框架，提升编程技能，不被行业所淘汰，而且掌握数据结构和算法之后看待问题的深度和角度都会不一样了。

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

## 一、数据结构 ##

### 1. 什么是数据结构 ###

[数据结构][Link 1]是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

我听过一堂很有意思的课程，以如何在书架上摆放图书为例讲述数据结构，比如你是图书管理员，现在有几千本、几万本书要你去管理，把它们放到书架上，你会怎么做？

*  方式一：随便放
    
     *  这种方式放置图书的好处就是方便，哪里有空位就把书放到哪里，你放书是方便了，但是某天一个同学让你去找一本书你怎么找？从头找，一本一本的看，找到最后发现居然没这本书，然后不好意思的跟别人说你们这没这本书，这不就耽误了大家的时间了吗，你找书还累。
 *  方式二：按照书名的拼音字母顺序排放
    
     *  这种方式放置图书的好处就是别人让你找书的时候你不再需要一本本的去遍历所有的图书了，可以采用二分法，快速的定位到你要找的书在哪，但是问题是，你每往里面插入一本书都需要将排在这边书之后的所有书都往后摞一格，这也不行啊。
 *  方式三：把书架划分成几块区域，每块区域指定摆放某种类别的图书，在每种类别内，按照书名的拼音字符顺序排放
    
     *  这种方式相比前面两种就科学很多，首先你插入新书，先定书的类别，再二分法查找需要插入的位置，移出空位，查找书也一样，先定类别，再二分法去找书，这种方法就算方式一和方式二的中庸之选了，既不会特别难找某一本书，也不会特别难去插入一本书，但是问题是每个类别的书要分配多大空间，类别要怎么分，越细越好吗？

从上述怎么放书的例子，我们可以看到没有一种完美的方式解决这个问题，假如你管理的就几本书，方式一肯定是最佳选择，数据结构就像是摆放这些图书的方式，在特定的情况下寻找最佳的解决方式才是我们所需考虑的，也是学习数据结构的初衷。

## 二、算法 ##

### 1. 什么是算法 ###

[算法（Algorithnm）][Algorithnm]是指解题方案的准确而完整的描述，是一系列解决问题的有限指令（每一条指令必须有明确的目标，不可以有歧义，在计算机处理的能力范围内，且不依赖任何一种计算机语言实现），接受一些输入（有些情况下也不需要输入）在一定步骤之后终止产出输出。

### 2. 什么是好的算法 ###

一个好的算法的一般得从空间复杂度和时间复杂度综合衡量，做到 “省内存” 和 “效率高”

**空间复杂度 S(n)**：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

**[时间复杂度][Link 2] T(n)**：根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年等不到运行结果。

这两个指标和要处理数据的规模，是直接相关的

以下我就例举两个例子来说明以上两个两个问题：

例1：写程序实现一个函数 printN，使得传入一个正整数为 n 的参数后，能顺序打印从 1 到 n 的全部正整数

实现一：循环实现

public static void printN(int n) {
        
            for (int i = 1; i <= n; i++) {
        
                System.out.println(i);
            }
        }

实现二：递归实现

public static void printN(int n) {
        
            if (n!=0) {
        
                printN(n-1);
                System.out.println(n);
            }
        }

从代码上看，这两种方式实现的所用的代码量都差不都，循环实现的方式还多使用了一个变量 i，那他们的效率是否一样呢？

当 n 比较小的时候，两者效率都差不多，但是当 n 比较大的时候，递归程序非正常终止掉了，因为递归的程序对空间的占用比较多，如果 n 特别大的时候计算机是吃不消的，可以来分析下这两种方式实现的程序都开辟了多少内存空间。

*  实现一：不管 n 有多大，它所占用的空间都是固定，并不会随着 n 的增长而增长，所以它的空间占用是一个常量，T(n) = c。
 *  实现二：当传入 n 时，发现 n 不等于 0，又会去递归调用该函数本身，每调用一次就需要开辟一块内存空间，n 有多大就会开辟 n 块的内容资源，空间复杂度是 T(n) = c·n，假设 n 是 100000，那么你计算机就得为其开辟 100000 块的内存空间导致内存溢出，程序非正常终止。

例2：写程序计算给定多项式在给定点 x 处的值

![在这里插入图片描述][069614a603c541aab115eb70b5c6bdd2.png_pic_center]

实现一：直接用代码翻译

public static double fun1(int n, double[] a, double x) {
        
            double p = a[0];
            for (int i = 1; i <= n; i++) {
        
                p += (a[i] * Math.pow(x, i));
            }
            return p;
        }

实现二：巧妙的使用结合律，每一次把 x 当成公因子提出来

![在这里插入图片描述][cafbccccd7c64effaa3b3b6248e8072b.png_pic_center]

public static double fun2(int n, double[] a, double x) {
        
            double p = a[n];
            for (int i = n; i > 0; i--) {
        
                p = a[i - 1] + x * p;
            }
            return p;
        }

那这两种方式实现的程序在效率上又会有什么差距呢？可以运行下测试他们所用的时间，我这里是让它计算同一组数据 一百万次所花费的时间为例：

测试代码如下

public static void main(String[] args) {
        
            double[] a = {
        1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0};
            int n = a.length-1;
            double x = 8.0;
    
            long fun1StartTime = System.currentTimeMillis();
            for (int i = 0; i < 1000000; i++) {
        
                double v = fun1(n, a, x);
            }
            long fun1EndTime = System.currentTimeMillis();
    
            System.out.println("实现一运行 1000000 所用时间：" + (fun1EndTime-fun1StartTime));
    
            long fun2StartTime = System.currentTimeMillis();
            for (int i = 0; i < 1000000; i++) {
        
                double v = fun2(n, a, x);
            }
            long fun2EndTime = System.currentTimeMillis();
    
            System.out.println("实现二运行 1000000 所用时间：" + (fun2EndTime-fun2StartTime));
    
        }

运行结果如下：

![在这里插入图片描述][7f1bd51eb2eb45728a86dfc7e2ad4e2f.png_pic_center]

可以明显看到实现二的方式比实现一的方式效率高很多，同样的代码量为什么会有这么大的差距呢？

计算机在处理 `加减` 的效率比处理 `乘除` 的效率高，在处理 `位运算` 的效率比处理 `加减` 的效率高

在忽略加减运算的条件下，实现一处理了 `(n^2 + n)/2` 次乘法运算，时间复杂度 `T(n) = C·n^2 + C·n` ；实现二处理了 `n` 次乘法运算，时间复杂度 `T(n) = C·n` ，当 n 足够大的时候，实现二一定会比实现一的程序快很多。

### 3. 复杂度分析 ###

在分析一般算法的效率时，我们经常关注下面两种复杂度

*  最坏情况复杂度 T worst(n)
 *  平均复杂度 T avg(n)

但是什么是平均？平均复杂度是很难估算的，所以我们更关注最坏情况的复杂度

**大O复杂度表示法：**

算法的执行时间与每行代码的执行次数成正比，用`T(n) = O(f(n))`表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而 n 往往表示数据的规模。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为 f(n) ，那么时间复杂度为 O(f(n))

例如：选择排序 -> 一个大小为 n 的数组进行从小到大的排序

思路：在 0 ~ n-1 上寻找一个最小值，找到了就放到 0 位置上，然后再在 1 ~ n-1 上面找一个最小值放到 1 位置上，依次类推，最后就能够将数组中的顺序给排列好

代码如下：

public static void selectionSor(int[] arr) {
        
            if (arr == null || arr.length < 2) {
        
                return;
            }
    
            for (int i = 0; i < arr.length; i++) {
        
                int minIndex = i;
                for (int j = i + 1; j < arr.length; j++) {
        
                    minIndex = arr[j] < arr[minIndex] ? j : minIndex;
                }
                swap(arr, i, minIndex);
            }
        }
    
        public static void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

在这样的一个过程中，首先在 0 ~ n-1位置上的每一个数，我们都得看一眼吧，第一步 for 循环中就看了 n 眼，然后看到的每一个数都要和之前找到的最小数进行对比，0~n-1个数中，一开始的数不需要比较，然后之后的数字就需要进行比较，姑且假设最坏情况下它也比较了 n 次，然后最后一步进行了 1 次交换操作，第二次循环看了 n-1 次，比较了 n-1 次，进行了 1 次交换操作 … 依次类推，它看了 n + (n-1) + (n-2) +…+ 1 次（等差数列），比较了 n + (n-1) + (n-2) +…+ 1 次（等差数列），和交换了 n 次，一共做了 an^2 + bn + c 次操作，它的时间复杂度就是根据这个表达式来着的，按照上述规则，`在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数`，那么剩下的就是 `n^2`，所以说选择排序的复杂度就是 `O(n^2)`

#### 1. 常数时间 ####

若对于一个算法，T(n) 的上界与输入大小无关，则称其具有常数时间，记作 `O(1)` 时间。

比如说数组的寻址操作，它就是一个常数操作，和数组的数据量没什么关系，只是将 i 位置的数据拿出来，计算机在拿 i 处的数据时，只是计算了一个偏移量将上面的数据拿出来而已，这个操作对于计算机而言就是一个固定的时间。

int a = arr[i];

#### 2. 线性时间 ####

如果一个算法的时间复杂度为 `O(n)` ，则称这个算法具有线性时间，或 O(n) 时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如：一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。

代码如下：

public static int linear(int[] arr) {
        
            int sum = 0;
            for (int i = 0; i < arr.length; i++) {
        
                sum += arr[i];
            }
            return sum;
        }

#### 3. 对数时间 ####

若算法的T(n) =`O(logn)`，则称其具有对数时间。对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小，常见的具有对数时间的算法有二叉树的相关操作和二分搜索。例如：在一个有序列表中查找某个值的位置，我们通过二分法进行查找。

代码如下：

public static int logarithm(int[] arr,int num) {
        
            int left = 0;
            int right = arr.length-1;
            while (left <= right) {
        
                int mid = (left + right)/2;
                if (arr[mid] > num) {
        
                    right = mid - 1;
                } else if (arr[mid] < num) {
        
                    left = mid + 1;
                } else {
        
                    return mid;
                }
            }
            return -1;
        }

在最糟糕的情况下，我们通过二分法拆分 x 次后，最后一个元素就是我们要找的元素。

#### 4. 次方时间 ####

`O(n^k)` 表示 k 次方时间复杂度，一个算法的时间将会随着输入数据 n 的增长而呈现出 k 次关系增加。

代码如下：

public static int power(int n) {
        
            int sum = 0;
            for (int i = 0; i < n; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    sum = sum + i + j;
                }
            }
            return sum;
        }

上面的程序中，是个两层循环的程序，函数的执行时间和n是二次方的关系：f(n) = n^2 + 2；

对于这种类型的程序，我们可以用 `O(n^2)`表示。不过，循环嵌套除了这种两层循环之外，还会有三层、四层…k 层循环，对应的其复杂度就是`O(n^3) 、O(n^4)...O(n^k)`。

#### 5. 指数时间 ####

`O(2^n)`表示指数复杂度，随着 n 的增加，算法的执行时间成倍增加，它是一种爆炸式增长的情况，例如：使用动态规划解决旅行商问题

**什么是旅行商问题？**

假设有一个旅行商人要拜访n+1个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。

这个我就不再举例了，如果你想探究下这个问题可参见以下文章：

[用动态规划法求解TSP问题][TSP]

[使用动态规划求解旅行商问题][Link 3]

#### 6. 阶乘时间 ####

若算法的T(n) =`O(n!)`，则称其具有阶乘时间。其中最典型的例子还是旅行商问题，不同于上一个指数时间的计算的方法，使用最暴力的穷举法得出的对应复杂度就是 `O(n!)`

这个我暂时也不举例了，本人也没有好好研究过这个问题！！

### 4. 常见复杂度比较 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5aSa5Yqg54K56L6j5Lmf5rKh5YWz57O7_size_16_color_FFFFFF_t_70_g_se_x_16_pic_center]

在上图中，我们可以看到当 n 很小时，复杂度相差不大，但是当 n 增大时，就能看到很明显的区别：

O(1) < O(logn) < O(n)  < O(nlogn) < O(n^2)  < O(2^n) < O(n!)

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

参考：  
算法时间复杂度分析：大O表示法 [https://zhuanlan.zhihu.com/p/320354735][https_zhuanlan.zhihu.com_p_320354735]  
大O表示法(复杂度分析) [https://blog.csdn.net/weixin\_38483589/article/details/84147376][https_blog.csdn.net_weixin_38483589_article_details_84147376]  
常用时间复杂度整理 [https://blog.csdn.net/u010010664/article/details/78834695][https_blog.csdn.net_u010010664_article_details_78834695]  
常用算法和复杂度总结 [https://developer.aliyun.com/article/327694][https_developer.aliyun.com_article_327694]

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450?fr=aladdin
[Algorithnm]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025?fr=aladdin
[Link 2]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E6%80%A7/5930669?fromtitle=%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&fromid=1894057&fr=aladdin
[069614a603c541aab115eb70b5c6bdd2.png_pic_center]: https://img-blog.csdnimg.cn/069614a603c541aab115eb70b5c6bdd2.png#pic_center
[cafbccccd7c64effaa3b3b6248e8072b.png_pic_center]: https://img-blog.csdnimg.cn/cafbccccd7c64effaa3b3b6248e8072b.png#pic_center
[7f1bd51eb2eb45728a86dfc7e2ad4e2f.png_pic_center]: https://img-blog.csdnimg.cn/7f1bd51eb2eb45728a86dfc7e2ad4e2f.png#pic_center
[TSP]: https://blog.csdn.net/wmy01234/article/details/105618834
[Link 3]: https://www.cnblogs.com/youmuchen/p/6879579.html
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5aSa5Yqg54K56L6j5Lmf5rKh5YWz57O7_size_16_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/7e7a9941bde94824b71322814cb2157b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5aSa5Yqg54K56L6j5Lmf5rKh5YWz57O7,size_16,color_FFFFFF,t_70,g_se,x_16#pic_center
[https_zhuanlan.zhihu.com_p_320354735]: https://zhuanlan.zhihu.com/p/320354735
[https_blog.csdn.net_weixin_38483589_article_details_84147376]: https://blog.csdn.net/weixin_38483589/article/details/84147376
[https_blog.csdn.net_u010010664_article_details_78834695]: https://blog.csdn.net/u010010664/article/details/78834695
[https_developer.aliyun.com_article_327694]: https://developer.aliyun.com/article/327694