【数据结构 | 入门】 入坑篇 （浙江大学数据结构学习笔记）

在这里插入图片描述

🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。

本文学习笔记 - 视频地址 ： 数据结构-浙江大学

文章目录

• 一、什么是数据结构
• 二、简单循环例子
• 三、多项式例子
• 四、数据结构
• 五、算法
  • 5.1 描述算法好坏
  • 5.2 复杂度的渐进表示法
  • 5.3 最大子列和问题
    • 算法一 - 暴力枚举
    • 算法二 - 减少重复
    • 算法三 - 分而治之
    • 算法四 - 在线处理

一、什么是数据结构

在这里插入图片描述

实际上，数据结构与算法经常是在一起，好的数据结构可以决定好的算法

有一个简单的例子，比如我有一堆书，我需要你将书本放入书架，那么你想要怎么放呢？

1. 方法1： 随便放 但是查找的时候非常麻烦！
2. 方法2： 按照书名的拼音字母顺序排放 查找的时候就可以使用 二分查找!! （ 也叫截半查找） 问题：插入新书，需要移动很大一部分书
3. 实际上，我们在图书馆都是按照分科分别区域，每个分科按照书名的拼音字母顺序 好处：大大降低规模，插入于查找都小了很多

类别分细，查找方便，但管理麻烦，同样，类别分粗一点，查找麻烦，管理方便 所以综上所述， 数据结构的组织方式决定了方式的效率

二、简单循环例子

题目很简单: 实现一个函数，传入正整数N，打印从1到N的全部正整数

循环实现很简单，我们重点看递归实现（由于递归更加简洁易懂，所以程序员比较喜欢递归算法）

在这里插入图片描述

递归更加简洁，少定义了一个变量，我们动手写代码跑代码测试，从N到100，100000，1000000，1000000…

1. 循环实现

在这里插入图片描述

可以看到，程序慢慢打印结果，而

1. 递归实现

在这里插入图片描述

输入100000后却直接推出程序，这是为什么呢？发生了神马事情呢？ 因为递归的占用的空间是非常恐怖的，这次递归把空间都吃掉，所以会异常退出结果

所以综上所述， 解决办法的效率与空间的利用效率有关

三、多项式例子

在这里插入图片描述

很显然，我们会很快写出如上代码，但实际上更加专业的方式如下

在这里插入图片描述

那为什么我们说第二个实现的比第一个好呢？是因为所花费的时间大小，我们可以用使用C语言的计时器

在这里插入图片描述

我们算算他们的时间，代码如下

在这里插入图片描述

在这里插入图片描述

这是由于运行速度非常快，一个tick无法检测到。那我们可以让他跑10000此，加长时间，最后计算平均时间即可！

在这里插入图片描述

在这里插入图片描述

显然，不在同一个数量级

所以综上所述， 解决办法的效率与算法的巧妙程度有关

四、数据结构

回到开头，什么是数据结构

在这里插入图片描述

逻辑结构： 一对一： 线性结构 一对多： 树 多对多: 图

物理结构： （在计算机存储） 数组 链表

在这里插入图片描述

实际上，不同数据结构的组织方式决定了他们的操作方式

矩阵例子：

在这里插入图片描述

抽象在哪里呢？比如a 是矩阵元素的值，那这个值是什么的byte,int,double呢？

在这里插入图片描述

在这里插入图片描述

抽象是问题变得简单

五、算法

英文名称叫做 algorithm

在这里插入图片描述

一个简单的选择排序

在这里插入图片描述

在这里插入图片描述

5.1 描述算法好坏

这是由两个指标 ， 空间复杂度s(n) 与时间复杂度 t(n)衡量的

在这里插入图片描述

例子一：

在这里插入图片描述

这是前面的例子，在打印十万次后，程序非正常退出了

原理：

在这里插入图片描述

对N来说，必须要直到N=0，函数才能有结果，函数一直被调用，每一次调用就要存贮使用一个空间，所有空间复杂度在这里为

而前面的循环算法，只有一个临时变量和一个循环，并没有函数调用等，占用空间始终是一个固定的

例子二：

在这里插入图片描述

这是我们之前求多项式的算法，我们也通过时间测量第二个时间快很多，那实际原理是怎么样的呢？

实际上，机器的加减法运算要比乘除快很多，所以我们在数函数做了多少次乘除，加减法忽略不计。

我们数数其中的乘除

在这里插入图片描述

分析算法效率，我们经常关注两种算法复杂度

在这里插入图片描述

5.2 复杂度的渐进表示法

实际上，我们并不需要对算法做非常精细的表示，只要知道其趋势，渐近表示法由此而来

在这里插入图片描述

我们看看不同函数的输入规模

zz

对于

来说显然是最好的，增长最慢，其下标是2还是10并没有影响，只是一个倍数变化

在这里插入图片描述

可以看到复杂度的变化在数据规模庞大时是差别很大的

在这里插入图片描述

复杂度分析小窍门

在这里插入图片描述

5.3 最大子列和问题

算法一 - 暴力枚举

在这里插入图片描述

可以看到时间复杂度很大，实际上该算法，在计算时对总和重复计算了 ，在J加了1之后，我们只要加一个元素就好了，不需要多加一个循环。

算法二 - 减少重复

在这里插入图片描述

此时时间复杂度 为 O(n2)小了一个数量级，作为一个程序员，看到O(n2) 我们总希望化为 O(log n)，

算法三 - 分而治之

第三个算法： 分而治之， 大概思路为将一个大问题分为多个小问题，最后再将对应结果其合在一起。

我们将数组分几份，那么这几份所求的结果中最大的便是最终结果。 我们看一个例子

在这里插入图片描述

我们从中间切割一半，分为左右各一半，再从左右再次分半，直到分至一个结果，我们看第一层，分别以两个元素以一小块，选取出结果为 4 5 2 6,在往上增加元素至最大值，二次选取结果为6 8 ，在网上选取就是11，可以看到方法很好理解，麻烦一点是在于程序的实现比较长。

那让我们分析一下改算法的复杂度是多少呢？

我们由于分半了，所以数据规模对应分半，且最后一层是便利整个数组，复杂度为

所以对应复杂度方程如下图底部

在这里插入图片描述

我们对对应公式进行递推展开，一直展开到数据规模为1

在这里插入图片描述

其中

则

, 在前面中提到两个复杂度式子相加，则取最大值，所以该算法复杂度为

，但此时该算法还不是最快的！

算法四 - 在线处理

在这里插入图片描述

可以看到处理非常的巧妙，这便是最快最好的算法（至少要便利一次数，所以最低也是O(n)) 同时最快最好的算法也有可能有副作用，正确性不是特别的明确（他人理解比较困难）,因为此时处理结果是一个一个，当停止时返回当前处理结果，所以称之为在线处理

在这里插入图片描述