作为一名普通的二本学校,我在很早之前就有一个目标,那就是大学之后好好找一个软件开发工作。因此学习了很多的编程基础,不过近几天面试发现,技术官总是喜欢问你算法知识。编程语言不断变化,但是很底层的知识与算法密切相关,算法也就是体现程序员内功所在。因此,从此我要好好学算法。

本笔记参考马士兵老师的视频教程:https://www.bilibili.com/video/av46562560

一、基本概念

算法是数据结构与算法的简称

1.什么是数据结构?

Data Structure
简单的理解,数据结构就是:存储数据的不同方式
19060701.png

假如我们把5个数据比作5个鸡蛋,我们可以把它们放到一个管子里,也可以把它们放到一个框子里,这就是不同的存储方式。存储数据的不同方式就是不同的数据结构。

引申:加入我们有2,4,7,1,6,3,5个数,我们如何来存储?

方式一:我们最容易想到的方式就是把其个数挨个紧紧排在一起,中间没有任何空隙,如图所示,在计算机中我们叫做数组(实际上,)。数组的每一个存储单元大小都一样,每一个整数放到一个单元格里面。
深度截图_选择区域_20190607134827.png

方式二:我们还可以使用另外一种方式,每一个小格除了存储自己的数据以外,还存着指向下一个小格的指针(链条),这样的存储方式叫做链表。

总结:数据的存储方式有很多种,对于不同的问题我们会采取不同的存储方式,这就是我们要学的数据结构。

2.什么是算法(Algorithm)?

算法是同一个问题的不同解决方法。
如下面的计算题:1+2+3+......+99=?

方式一:我们使用最简单的方式就是1先加2,再加3,再加4,以此类推。
方式二:我们还可以分别计算1加99,2+98,3+97,以此类推。

同一个问题,我们有不同的解决办法,这就是算法。而算法往往是针对特定的数据结构的。

假设1:对于1中的链表这种数据结构,我们如何往链表里面的7和1插入一个0?
这时候我们只需要将7和1中的链条打断,让7中的链条指向0,0中的链条指向1,这时候就构成了一个新的链条,这就完成了。

假设2:对于1中的数组,我们如歌在7和1之间插入0?
那么这个算法就稍微麻烦一些了。数组之间没有空隙,我们插入不了,因此可以采取以下办法:我们重新分配一块新的空间,这是的新空间要比原来的空间要大一个单元格,也就是一个单位的数据大小。这时候先把2,4,7复制下来,再把0插进去,最后把1,6,5,3复制下去,如下图所示:
深度截图_选择区域_20190607141257.png

由上面我们可以看出,对于插入算法来说,链表要比数组简单的多。当然,不能说数组就不如链表,有很多的操作数组要比链表快得多,比如说我们想访问第6个数。对于链表来说我们必须从第一个数开始,先找到第一个数,再根据第一个数顺着链条往后找,最终才能找到。二对于数组来说,找第6个数就很简单,只要知道单元格的大小,直接往后跨越6个单元格,就可以找到第6个数,所以查找对于数组来说,要比链表快。

所以,对不同的数据结构,在不同的应用场景中有不同优点和缺点,所以,选择什么样的数据结构,要根据特定的问题来决定。

总的来说,数据结构就是存储数据的不同方式,算法就是解决问题的不同方法,而算法往往是针对不同的数据结构的。

二、如何测算算法的优劣?

时间测算:1.计算算法时间差;幅度不够循环来凑。对于一个问题,完成同样结果,我们认为所用时间越少,算法越好;
空间测算:对于一个问题,如果完成同样的结果,我们认为,占用系统的空间越少,算法越好,占用系统空间越大,算法越不好。

1.我们如何秒速算法的优劣?Big O

O(Big O):Big O(也可以读作“大O”)用来标识复杂度。

什么是时间复杂度?计算机解决一个问题执行的时间,随着问题规模的扩大,时间的变化的规律。
什么是空间复杂度?计算机解决一个问题做占用的空间,随着问题规模的扩大,空间的变化规律。

假设一:如果数组规模为10,需要找数组中的最后一个数,现在数组规模变成10万,需要找数组中的最后一个数。时间其实是一样的,这时候把时间复杂度称为O(1),O(1)表示时间复杂度是一个常数,不管数组规模扩大多少,我们需要找第几个数,所用时间是一个固定的值,此时记为O(1)。

假设二:如果要访问链表中某个位置的值,这时候时间复杂度为O(n)。一般时间复杂度我们都讲的是最差的情况,在链表中,找第一个数的时间复杂度还是为O(1),而我们一般考虑的是找最后一个数的情况。所以此时复杂度为O(n)。

时间复杂度一般都有什么?
n2,n3,log n

假设三:求一个数组的平均数?求一个数组的平均数,我们先把所有数加起来,所以一个数组规模要扩大,我们要加的数随之扩大,因此时间复杂度是O(n)。

2.思考:用O表示时间复杂度?

a.查找数组最后一个位置上的数
b.查找链表最后一个位置上的数
c.对数组求和
d.查找数组的最大值