♂️ 个人主页: @计算机魔术师
作者简介:CSDN内容合伙人,全栈领域优质创作者。
本文学习笔记 – 视频地址 : 数据结构-浙江大学
文章目录
- 一、什么是数据结构
- 二、简单循环例子
- 三、多项式例子
- 四、数据结构
- 五、算法
- 5.1 描述算法好坏
- 5.2 复杂度的渐进表示法
- 5.3 最大子列和问题
- 算法一 – 暴力枚举
- 算法二 – 减少重复
- 算法三 – 分而治之
- 算法四 – 在线处理
一、什么是数据结构
实际上,数据结构与算法经常是在一起,好的数据结构可以决定好的算法
有一个简单的例子,比如我有一堆书,我需要你将书本放入书架,那么你想要怎么放呢?
方法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 ∗ ns(n)=c*ns(n)=c∗n
而前面的循环算法,只有一个临时变量和一个循环,并没有函数调用等,占用空间始终是一个固定的
例子二:
这是我们之前求多项式的算法,我们也通过时间测量第二个时间快很多,那实际原理是怎么样的呢?
实际上,机器的加减法运算要比乘除快很多,所以我们在数函数做了多少次乘除,加减法忽略不计。
我们数数其中的乘除
分析算法效率,我们经常关注两种算法复杂度
5.2 复杂度的渐进表示法
实际上,我们并不需要对算法做非常精细的表示,只要知道其趋势,渐近表示法由此而来
我们看看不同函数的输入规模
对于 l o g nlog nlogn 来说显然是最好的,增长最慢,其下标是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 g2nk= log_2nk=log2n 则 T ( N ) = O ( n ) + c n ∗ l o g2nT(N) = O(n) + cn*log_2nT(N)=O(n)+cn∗log2n, 在前面中提到两个复杂度式子相加,则取最大值,所以该算法复杂度为 n ∗ l o g2nn*log_2nn∗log2n,但此时该算法还不是最快的!
算法四 – 在线处理
可以看到处理非常的巧妙,这便是最快最好的算法(至少要便利一次数,所以最低也是 O ( n )O(n)O(n))
同时最快最好的算法也有可能有副作用,正确性不是特别的明确(他人理解比较困难),因为此时处理结果是一个一个,当停止时返回当前处理结果,所以称之为在线处理
✨谢谢你的阅读,您的点赞和收藏就是我创造的最大动力!✨