数据结构与算法:学习的必要性解析

发表时间: 2020-12-25 19:14

本文出自《愚公要移山》个人博客中,地址www.javachat.cc

收录于《手牵手一起学习数据结构与算法》专栏

前言:我们到底该不该学习算法与数据结构?

1、真的应该学习

这个问题本身就不是个问题,所有人都在强调数据结构与算法比较重要,但是好像平时也没用到,无法直观的去感受它的重要性,于是把学习重心放在了常见的哪些框架身上,似乎只要熟悉了哪些框架的API,编程就会所向披靡。

我举一个我自身的例子,我本科期间想做一个APP,主要是在线预约的功能,既然是在线预约,用户多了之后那就需要排队,当时也不管三七二十一,不管哪种结构,那就先试试ArrayList,当然这种数据结构也能解决,但是当真正操作其增删改查的时候才发现ArrayList确实是比较麻烦一点。

在网上开始问各种大佬,统一回复的一句话是,你现在学数据结构了吗?你数据结构咋学的?现在想想真的是留下了悔恨的眼泪。

既然数据结构与算法重要,到底哪个地方重要呢?下面就来说说:

2、重要性体现

第一:面试

面试确实是第一个体现的点,因为你会发现,面试外企的时候他们第一件事就是啥都不问,上来就是几道算法题。包括国内的字节跳动。现在的阿里、腾讯、华为、美团。凡是大家知道的那些大厂基本上上来就是先敲代码。可以看出国内外大厂对于算法与数据结构的看重。

第二:工作

现在的大厂api框架基本上背后的逻辑就是基于算法实现的。其实算法的种类有很多,比如说机器学习、神经网络算法,还有java中的排序算法,互联网的商品推荐、股票预测其背后的逻辑都是算法。就算是熟悉的那些框架,背后的逻辑也是数据结构与算法。我们敲代码解决问题的过程当中也是算法的集中体现。

第三:学习

学习数据结构与算法的目的,别人我不知道,对我目前来说,是想了解哪些常见框架,常见机制背后的运行逻辑。进而为以后创造一个更加强大的产品做铺垫。任何一个新东西,都是先了解,再模仿,最后再创造的过程。

第四:应付学业

我之前大学学习这门课的时候,学分比重还是比较大的,好几年过去了,不知道现在变没变。不过最起码考研或者是期末考试,这门课都是必须要学习的一门课。可见学校也比较重视。

一、算法与数据结构到底是个什么东东?

在这里我不想去解释哪些常见的名词了,像什么是数据项、数据对象、元素等等这些概念。稍微有点基础的人,对这些概念都应该很清楚,毕竟都是中国人。我主要想说一下,我们到底该如何理解数据结构与算法。

1、什么是数据结构?

高中的时候都学习过化学,什么水的结构,碳原子的结构,这些分子、原子之间不是杂乱无章的,我们总是可以归纳分析出一些规律。对于计算机中的数据元素而言,这些数据元素也不是孤立的,总是有一种或者是几种的内在联系。

数据结构:数据元素相互之间一种或者多种关系的表示

既然数据元素之间有某种关系,那这种关系到底是什么呢?这里直接总结了一下。

可以看出分两类,表示了这些数据元素之间的关系。我们在学习数据结构的时候,其实就是学习这些数据元素到底有哪些关系。

2、什么是算法

宋丹丹和赵本山有过一个小品,说如何把大象关进冰箱里。第一步先把冰箱门打开,第二步把大象装进去,第三步,把冰箱门关上。整个简单的流程完美的体现了算法的思想。标准定义:

算法:解决问题的步骤的描述

就这么几个字,其实就是描述过程的。当然解决问题的方法有很多,因此算法也有很多种,就比说我们常见的排序算法,就简简单单为了从小到大排序,哪些科学家们活活的搞出了十几种。每一种排序方式都是一个算法。

3、数据结构与算法的关系(重点)

我们经常会听到有人说:程序=算法+数据结构,某位大佬科学家就提出了这几个字还得了图灵奖。大学的时候知道这件事还让我一度怀疑图灵奖也不过如此。嘿嘿,不过现在不敢说了,看的越多,越觉得这个简单地公式蕴含了无数的道理。

既然是讨论他们之间的关系。我们再来看个例子,毕竟例子各位才理解的更加清楚。假如我国要在多个城市之间新建一条高铁。要求是能够连接多个城市,而且成本最低。OK,好了,现在就这么个需求,我们来分析。

第一目的:修建铁路

第二要求:连通所有城市,成本最低。

我们一下子就能想到这是一个最小生成树问题,假如把每一个城市看成一个点,把城市之间的成本看成连线数字,就是找出来一个联通线。

目的其实就是为了找上图中的那条黑线。这里不是专门讲这个知识体系的。现在我们使用流程图看看,如果遇到了一个问题,我们是如何去使用程序去解决的。

从上图可以看出,为了要解决一个问题,首先我们要分析问题,然后确定解决思路,接下来设计或者是选择已有的算法,再然后就是确定实现的数据结构,最后就是代码的实现与优化。

数据结构在其中的位置可以看出,是为了更好地实现某种或者是某类算法。在讨论这门课的时候也会结合在一起去学习。

二、学习数据结构与算法我们最应该关注什么?

如果我们想要学好数据结构与算法,首先脑海中要时刻记住两个关键词汇,时间效率和空间效率。这个两个词汇贯穿了整个数据结构与算法的知识体系。

​ 数据结构可以助算法实现问题提供基础,算法为了解决某一问题必须要时间够快,空间足够节省。就好比我们为了能够在茫茫人海当中找寻另一半一样。首先时间要足够快,不能一个一个找,然后我们不可能把茫茫人海所有人的全部信息全给保存了,所以空间上还要足够节省。

那什么是时间效率和空间效率呢?通俗的理解就是:我们使用两个不同的程序去解决同一个问题,时间短的说明时间效率高,消耗空间小的说明空间效率高。

​ 我们在研究数据结构与算法的时候,其实就是选择不同的数据结构和不同的算法解决某一问题的同时尽可能的提升计算机的时间效率和空间效率。

1、首先看时间复杂度:

​ 想要了解时间复杂度,就需要先了解时间频度。一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

说白了时间复杂度就是描述时间的规模,比如说时间频度是T(n),时间复杂度就是O(n)。时间频度是T(n+n)的时候,时间复杂度还是O(n)。也就是他的时间规模就是n这个层次了。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度**。

常见的算法的时间 复杂度之间的关系为:

O(1)<O(logn)<O(n)<O(nlog n)<O(n2)<O(2n)<O(n!)<O(nn)

举个例子吧:

  a=0;                     //(1)     for(i=1;i<=n;i++)        //(2)        for(j=1;j<=n;j++)       //(3)         a++;              //(4)

语句(1)执行1次,

语句(2)执行n次

语句(3)执行n2次

语句(4)执行n2次

T(n) = 1+n+2n2= O(n2)

2、空间复杂度

空间复杂度就比较容易理解了,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个空间规模,我们用 S(n) 来定义。

空间复杂度比较常用的有:O(1)、O(n)、O(n²),

三、结论

在本文中,首先讨论了数据结构与算法的重要性,然后给出了数据结构与算法的理解,最后就是在学习数据结构与算法时,我们最应该关注的点。其中通过数据结构与算进的关系解决某一问题的流程是重点。在以后的文章中,也会惯用这一思路。这个思路是我在刷了力扣几百道题时总结出来的。

举个例子来说一下:

面试中经常会遇到一道题,那就是实现LRU(最近最久未使用)。我们按照上面的流程结构可以很清楚的把问题给解决掉,而不是死记硬背哪些现有的代码,比如

第一步分析问题,问题是实现最近最久未使用的算法,我们可以画图来看一下到底是个什么问题,

然后就是确定算法,比如说第一步我们该干嘛,第二步该干嘛等等。

接下来确定数据结构的时候,比如说可以自定义Node实现,还有java中为我们提供的LinkedHashMap等等。

最后就是根据数据结构的特点通过我们分析的算法流程去实现。

这样是不是有点清晰了。本专栏将持续推出。 也祝你在接下来的日子里更加灵活运用。