🤵?♂? 个人主页: @计算机魔术师
👨?💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。
本文学习笔记 - 视频地址 ： 数据结构-浙江大学
文章目录
一、什么是数据结构
实际上，数据结构与算法经常是在一起，好的数据结构可以决定好的算法
有一个简单的例子，比如我有一堆书，我需要你将书本放入书架，那么你想要怎么放呢？
-
方法1： 随便放
但是查找的时候非常麻烦！ -
方法2： 按照书名的拼音字母顺序排放
查找的时候就可以使用二分查找!!（ 也叫截半查找）
问题：插入新书，需要移动很大一部分书 -
实际上，我们在图书馆都是按照分科分别区域，每个分科按照书名的拼音字母顺序
好处：大大降低规模，插入于查找都小了很多
类别分细，查找方便，但管理麻烦，同样，类别分粗一点，查找麻烦，管理方便
所以综上所述， 数据结构的组织方式决定了方式的效率
二、简单循环例子
题目很简单: 实现一个函数，传入正整数N，打印从1到N的全部正整数
循环实现很简单，我们重点看递归实现（由于递归更加简洁易懂，所以程序员比较喜欢递归算法）
递归更加简洁，少定义了一个变量，我们动手写代码跑代码测试，从N到100，100000，1000000，1000000…
- 循环实现
可以看到，程序慢慢打印结果，而 - 递归实现
输入100000后却直接推出程序，这是为什么呢？发生了神马事情呢？
因为递归的占用的空间是非常恐怖的，这次递归把空间都吃掉，所以会异常退出结果
所以综上所述， 解决办法的效率与空间的利用效率有关
三、多项式例子
很显然，我们会很快写出如上代码，但实际上更加专业的方式如下
那为什么我们说第二个实现的比第一个好呢？是因为所花费的时间大小，我们可以用使用C语言的计时器
我们算算他们的时间，代码如下
这是由于运行速度非常快，一个tick无法检测到。那我们可以让他跑10000此，加长时间，最后计算平均时间即可！
显然，不在同一个数量级
所以综上所述， 解决办法的效率与算法的巧妙程度有关
四、数据结构
回到开头，什么是数据结构
逻辑结构：
一对一： 线性结构
一对多： 树
多对多: 图
物理结构： （在计算机存储）
数组
链表
实际上，不同数据结构的组织方式决定了他们的操作方式
矩阵例子：
抽象在哪里呢？比如a 是矩阵元素的值，那这个值是什么的byte,int,double呢？
抽象是问题变得简单
五、算法
英文名称叫做 algorithm
一个简单的选择排序
5.1 描述算法好坏
这是由两个指标 ， 空间复杂度s(n) 与时间复杂度 t(n)衡量的
例子一：
这是前面的例子，在打印十万次后，程序非正常退出了
原理：
对N来说，必须要直到N=0，函数才能有结果，函数一直被调用，每一次调用就要存贮使用一个空间，所有空间复杂度在这里为 s ( n ) = c ? n s(n)=c*n s(n)=c?n
而前面的循环算法，只有一个临时变量和一个循环，并没有函数调用等，占用空间始终是一个固定的
例子二：
这是我们之前求多项式的算法，我们也通过时间测量第二个时间快很多，那实际原理是怎么样的呢？
实际上，机器的加减法运算要比乘除快很多，所以我们在数函数做了多少次乘除，加减法忽略不计。
我们数数其中的乘除
分析算法效率，我们经常关注两种算法复杂度
5.2 复杂度的渐进表示法
实际上，我们并不需要对算法做非常精细的表示，只要知道其趋势，渐近表示法由此而来
我们看看不同函数的输入规模
对于
l
o
g
n
log n
logn 来说显然是最好的，增长最慢，其下标是2还是10并没有影响，只是一个倍数变化
可以看到复杂度的变化在数据规模庞大时是差别很大的
复杂度分析小窍门
5.3 最大子列和问题
算法一 - 暴力枚举
可以看到时间复杂度很大，实际上该算法，在计算时对总和重复计算了 ，在J加了1之后，我们只要加一个元素就好了，不需要多加一个循环。
算法二 - 减少重复
此时时间复杂度 为 O(n2)小了一个数量级，作为一个程序员，看到O(n2) 我们总希望化为 O(log n)，
算法三 - 分而治之
第三个算法： 分而治之， 大概思路为将一个大问题分为多个小问题，最后再将对应结果其合在一起。
我们将数组分几份，那么这几份所求的结果中最大的便是最终结果。
我们看一个例子
我们从中间切割一半，分为左右各一半，再从左右再次分半，直到分至一个结果，我们看第一层，分别以两个元素以一小块，选取出结果为 4 5 2 6,在往上增加元素至最大值，二次选取结果为6 8 ，在网上选取就是11，可以看到方法很好理解，麻烦一点是在于程序的实现比较长。
那让我们分析一下改算法的复杂度是多少呢？
我们由于分半了，所以数据规模对应分半，且最后一层是便利整个数组，复杂度为 O ( n ) O(n) O(n)
所以对应复杂度方程如下图底部
我们对对应公式进行递推展开，一直展开到数据规模为1
其中
k
=
l
o
g
2
n
k= log_2n
k=log2?n 则
T
(
N
)
=
O
(
n
)
+
c
n
?
l
o
g
2
n
T(N) = O(n) + cn*log_2n
T(N)=O(n)+cn?log2?n, 在前面中提到两个复杂度式子相加，则取最大值，所以该算法复杂度为
n
?
l
o
g
2
n
n*log_2n
n?log2?n，但此时该算法还不是最快的！
算法四 - 在线处理
可以看到处理非常的巧妙，这便是最快最好的算法（至少要便利一次数，所以最低也是
O
(
n
)
O(n)
O(n))
同时最快最好的算法也有可能有副作用，正确性不是特别的明确（他人理解比较困难）,因为此时处理结果是一个一个，当停止时返回当前处理结果，所以称之为在线处理
?谢谢你的阅读，您的点赞和收藏就是我创造的最大动力！?