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

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

文章目录

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

一、什么是数据结构


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

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

  1. 方法1: 随便放
    但是查找的时候非常麻烦!

  2. 方法2: 按照书名的拼音字母顺序排放
    查找的时候就可以使用 二分查找!! ( 也叫截半查找)
    问题:插入新书,需要移动很大一部分书

  3. 实际上,我们在图书馆都是按照分科分别区域,每个分科按照书名的拼音字母顺序
    好处:大大降低规模,插入于查找都小了很多

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

二、简单循环例子

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

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

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

  1. 循环实现

    可以看到,程序慢慢打印结果,而
  2. 递归实现

输入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)=cn

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

例子二:


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

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

我们数数其中的乘除

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

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)+cnlog2n, 在前面中提到两个复杂度式子相加,则取最大值,所以该算法复杂度为 n ∗ l o g2nn*log_2nnlog2n,但此时该算法还不是最快的!

算法四 – 在线处理


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

✨谢谢你的阅读,您的点赞和收藏就是我创造的最大动力!✨