什么是数据结构与算法?
数据结构
从广义上讲,数据结构
就是指一组数据的存储结构。
数据结构按照逻辑结构大致可以分为两类:线性数据结构和非线性数据结构。
线性结构
线性结构指的是数据之间存在着一对一
的线性关系,是一组数据的有序集合。线性结构有且仅有一个开始结点和一个结束结点
,并且每个结点最多只有一个前驱和一个后继。类比如现实生活中的排队。
线性结构常见的有:数组、队列、链表和栈等。
非线性结构
非线性结构指的是数据间存在着一对多
的关系,一个结点可能有多个前驱和后继
。如果一个结点至多只有一个前驱且可以有多个后继,这种结构就是树形结构。类比如公司的组织结构。如果对结点的前驱和后继的个数都不作限制,这种结构就是图形结构。类比如社交网络的朋友关系。
非线性结构常见的有:广义表,树,图等。
算法
从广义上讲,算法
就是操作数据的一组方法。
在我看来,算法就是基于某种数据结构为了达到某种目的的实现步骤。
常见的算法有哪些?
举个例子:
图书馆储藏书籍你肯定见过吧?
![]()
为了方便查找,图书管理员一般会将书籍分门别类进行“存储”并按照一定规律编号,这就是书籍这种“数据”的存储结构。那我们如何来查找一本书呢?有很多种办法,你当然可以一本一本地找,也可以先根据书籍类别的编号,是人文,还是科学、计算机,来定位书架,然后再依次查找。笼统地说,这些查找方法都是算法,算法有好坏之分,好的算法可以提高查找效率,节约查询时间;坏的算法对我们的查询没有任何帮助,甚至走进死循环。
数据结构和算法的关系
数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的算法就是没用的。
再举个例子,计算数字从1
到100
之和,使用循环我们可能会写出这样的程序:
public int count(int number){
int res = 0;
for (int i = 1; i <= number; i++) {
res += i;
}
return res;
}
如果这里的100
变成了十万、百万,那么这里计算量同样也会随之增加,但是如果使用这样一个求和的公式:
100 * (100 + 1) / 2
无论数字是多大,都只需要三次运算即可,算法可真秒!同样数据结构与算法是相互依存的,数据结构为什么这么存,就是为了让算法能更快的计算。所以学习数据结构与算法首先需要了解每种数据结构的特性,算法的设计很多时候都需要基于当前业务最合适的数据结构。
为什么要学习数据结构与算法?
当代程序员为了完成学业,为了更好的工作,为了写出更优秀的代码等等。反正只要你想学,总能找到坚持下去的理由。
![20190812021259-我爱学习](http://img.gorun996.com/images/2020/10/08/190206.jpg)
-
每年涌现出大量计算机开发人员,如何在这么多竞争者中突出重围,获取心仪的Offer,掌握数据结构与算法已经成为必杀利器之一。
-
不单单是为了面试,掌握数据结构和算法,不管对于阅读框架源码,还是理解其背后的设计思想,都是非常有用的,毕竟每个程序员都不想止步于 CRUD。
-
在平时的开发过程中,如果不知道这些类库背后的原理,不懂得时间、空间复杂度分析,你如何能用好、用对它们?存储某个业务数据的时候,你如何知道应该用 ArrayList,还是 Linked List 呢?调用了某个函数之后,你又该如何评估代码的性能和资源的消耗呢?
如何系统高效地学习数据结构与算法?
很多人都感觉数据结构和算法很抽象,晦涩难懂,宛如天书。还因为看不懂数据结构与算法,而一度怀疑自己太笨?正是这些原因,让我们对数据结构和算法望而却步。
其实学习数据结构和算法并不是很难,只要找到好的学习方法,抓住学习的重点,并且坚持下去,终有一天我们会征服这座高山。
那么学习数据结构与算法哪些是重点呢?
-
掌握复杂度分析方法 - 首先要掌握数据结构与算法中最重要的概念—
复杂度分析
,复杂度分析方法是考量效率和资源消耗的方法。所以,如果你只掌握了数据结构和算法的特点、用法,但是没有学会复杂度分析,那就相当于只知道操作口诀,而没掌握心法。 -
学习数据结构与算法是一个长期的过程,并且内容有很多,掌握了这些基础的数据结构和算法,再学更加复杂的数据结构和算法,就会非常容易、非常快。
-
数据结构与算法的诞生都是为了解决实际问题,无数先辈解决问题留下的宝贵财富,才有了我们我们今天看到的这么多数据结构与算法,如果你深入了解了,你也可以发明新的数据结构与算法。所以在学习的过程中一定要结合实际场景分析,才能抓住核心,记得更牢靠。
一些可以让你事半功倍的学习技巧
![初中物理好的学习习惯及学习技巧](http://img.gorun996.com/images/2020/10/08/190345.jpg)
1、边学边练,适度刷题
2、多问、多思考、多互动
3、打怪升级学习法
4、知识需要沉淀,不要想试图一下子掌握所有
复杂度分析
我们都知道,数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?这里就要用到我们今天要讲的内容:时间、空间复杂度分析。
![img](http://img.gorun996.com/images/2020/10/08/191729.jpg)
大 O 复杂度表示法
算法的执行效率,粗略地讲,就是算法代码执行的时间。但是,如何在不运行代码的情况下,用“肉眼”得到一段代码的执行时间呢?
这里有段非常简单的代码,求 1,2,3…n 的累加和。现在,我就带你一块来估算一下这段代码的执行时间。
public int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; i++) {
sum += i;
}
return sum;
}
从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,但是,我们这里只是粗略估计,所以可以假设每行代码执行的时间都一样,为 unit_time。在这个假设的基础之上,这段代码的总执行时间是多少呢?
第 2、3 行代码分别需要 1 个 unit_time 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n * unit_time 的执行时间,所以这段代码总的执行时间就是 (2n+2) * unit_time。可以看出来,所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
按照这个分析思路,我们再来看这段代码。
public int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum += i * j;
}
}
return sum;
}
我们依旧假设每个语句的执行时间是 unit_time。那这段代码的总执行时间 T(n) 是多少呢?
第 2、3、4 行代码,每行都需要 1 个 unit_time 的执行时间,第 5、6 行代码循环执行了 n 遍,需要 2n * unit_time 的执行时间,第 7、8 行代码循环执行了 n2遍,所以需要 2n2 * unit_time 的执行时间。所以,整段代码总的执行时间 T(n) = (2n2+2n+3)*unit_time。
尽管我们不知道 unit_time 的具体值,但是通过这两段代码执行时间的推导过程,我们可以得到一个非常重要的规律,那就是,所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。我们可以把这个规律总结成一个公式。注意,大 O 就要登场了!
我来具体解释一下这个公式。其中,T(n) 我们已经讲过了,它表示代码执行的时间;n 表示数据规模的大小;f(n) 表示每行代码执行的次数总和。因为这是一个公式,所以用 f(n) 来表示。公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
所以,第一个例子中的 T(n) = O(2n+2),第二个例子中的 T(n) = O(2n2+2n+3)。这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。
当 n 很大时,你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大 O 表示法表示刚讲的那两段代码的时间复杂度,就可以记为:T(n) = O(n); T(n) = O(n2)。
时间复杂度分析
如何分析一段代码的时间复杂度?
1、只关注循环执行次数最多的一段代码
2、加法法则:总复杂度等于量级最大的那段代码的复杂度
3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见时间复杂度实例分析
O(1)
: 常数级别,不会影响增长的趋势,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)
。O(logn)
: 对数级别,执行效率仅次于O(1)
,例如从一个100万
大小的数组里找到一个数,顺序遍历最坏需要100万
次,而logn
级别的二分搜索树平均只需要20
次。二分查找或者说分而治之的策略都是这个时间复杂度。O(n)
: 一层循环的量级,这个很好理解,1s
之内可以完成千万级别的运算。O(nlogn)
: 归并排序、快排的时间复杂度,O(n)
的循环里面再是一层O(logn)
,百万数的排序能在1s
之内完成。O(n²)
: 循环里嵌套一层循环的复杂度,冒泡排序、插入排序等排序的复杂度,万数级别的排序能在1s
内完成。O(2ⁿ)
: 指数级别,已经是很难接受的时间效率,如未优化的斐波拉契数列的求值。O(!n)
: 阶乘级别,完全不能尝试的时间复杂度。
空间复杂度分析
如果能理解时间复杂度的分析,那么空间度的分析就会显示的格外的好理解。它指的是一段程序运行时,需要额外开辟的内存空间是多少,我们来看下这段程序:
function test(arr) {
const a = 1
const b = 2
let res = 0
for (let i = 0; i < arr.length; i++) {
res += arr[i]
}
return res
}
我们定义了三个变量,空间复杂度是O(3)
,又是常数级别的,所以这段程序的空间复杂度又可以表示为O(1)
。只用记住是另外开辟的额外空间,例如额外开辟了同等数组大小的空间,数组的长度可以表示为n
,所以空间复杂度就是O(n)
,如果开辟的是二维数组的矩阵,那就是O(n²)
,因为空间度基本也就是以上几种情况,计算会相对容易。
常见的空间复杂度就是
O(1)
、O(n)
、O(n²)
,像O(logn)
、O(nlogn)
这样的对数阶复杂度平时基本用不到
总结
常见时间复杂度对比:
![常见时间复杂度对比](http://img.gorun996.com/images/2020/10/08/190718.jpg)
- 复杂度也叫渐进复杂度,包括时间复杂度和空间复杂度,用来分析算法执行效率与数据规模之间的增长关系
- 越高阶复杂度的算法,执行效率越低
- 常见的复杂度并不多,从低阶到高阶有:
O(1)
、O(logn)
、O(n)
、O(nlogn)
、O(n^2)