在学习数据结构与算法之前必须知道的几个概念:
什么是数据结构
:
为了解决问题,会将数据用特定的方式存储起来,存储的方式不同就会导致不同的算法处理,当然我们希望算法的效率越快越好,那么我们就需要考虑数据如何保存,这就是数据结构。
通俗的讲数据结构就是计算机存储、组织数据的方式,就像是锅碗瓢盆,它们都是来存放东西的。
什么是算法
:
一系列解决问题的清晰指令
,就像是厨房里的食谱,有特定的制作教程,根据这个教程就可以做出相应的菜。
数据结构与算法的关系
:
数据结构为算法提供服务,算法围绕数据结构操作。
如何判断一个算法是否可取
在作者身边的有一个真实的示例,一位后端工程师说:“昨天看到一个某某的算法,但是我觉得这个算法不太好...”。
这位后端工程师判断一个算法
是否可行单凭直觉,这样的判断肯定是不可取的,正确的判断方式是通过时间复杂度
和空间复杂度
。
认识时间复杂度
-
时间复杂度
,定性描述该算法的运行时间,通俗讲就是一个算法的循环次数。 -
时间复杂度
的表示用一个函数 O 表示,比如 O(1)、O(n)、O(logN)...,表示时间复杂度
的时候,不需要确却计算出这个数值。 -
两个
时间复杂度
相加时,取最大即可,例:O(1) + O(n) = O(n) -
两个
时间复杂度
相乘时,相乘即可,例:O(n) * O(logN) = O(n * logN)
- 它们的关系是:n! > 2^n > n^2 > nlogN > n > √n > logN > 1
认识空间复杂度
-
空间复杂度
,对一个算法在运行过程中临时占用存储空间大小的度量。 -
空间复杂度
的表示用一个函数 O 表示,比如 O(1)、O(n)、O(n^2)...。
认识每个数据结构
-
栈(Stack):一个后进先出的数据结构,JavaScript 中并没有栈,通过 Array 来实现栈的功能,通过方法
push
、pop
来实现入栈和出栈。 -
队列(Queue):一个先进先出的数据结构,JavaScript 中没有队列,通过 Array 来实现队列的功能,通过方法
push
、shift
来实现入队(enqueue
)和出队(dequeue
)。 -
链表(LinkedList):一个由多个元素组成的列表,元素存储是不连续,通过
next
指针连在一起,JavaScript 中没有链表,通过 Object 来实现链表的功能。 -
集合(Set):一个
无序
且唯一
的数据结构,ES6 中的集合, 名Set
。 -
字典(Map):一个用
键值对
存储唯一值
的数据结构,ES6 中的字典,名Map
-
树(Tree):一种分层数据的抽象模型,JavaScript 中没有树,通过 Array 和 Object 构建树。
-
图(graph):一种网络结构的抽象模型,是一组由边连接的节点,JavaScript 中没有图,通过 Array 和 Object 构建图。
-
堆(Heap):一种特殊的完全二叉树,所有的节点大于等于(最大堆)或小于等于(最小堆)它的子节点,JavaScript 中没有堆,通过 Array 表示堆。
认识常见算法
-
链表的遍历、删除链表节点
-
树和图的深度/广度优先遍历
-
搜索排序
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 顺序搜索
- 二分搜索
认识常见算法设计思想
- 分而治之
- 动态规划
- 贪心算法
- 回溯算法
最后,希望读者可以通过本篇文章对数据与结构
有一定的认识和觉悟。。。。。。