在学习数据结构与算法之前必须知道的几个概念:

什么是数据结构

为了解决问题,会将数据用特定的方式存储起来,存储的方式不同就会导致不同的算法处理,当然我们希望算法的效率越快越好,那么我们就需要考虑数据如何保存,这就是数据结构。

通俗的讲数据结构就是计算机存储、组织数据的方式,就像是锅碗瓢盆,它们都是来存放东西的。

什么是算法

一系列解决问题的清晰指令,就像是厨房里的食谱,有特定的制作教程,根据这个教程就可以做出相应的菜。

数据结构与算法的关系

数据结构为算法提供服务,算法围绕数据结构操作。

如何判断一个算法是否可取

在作者身边的有一个真实的示例,一位后端工程师说:“昨天看到一个某某的算法,但是我觉得这个算法不太好...”。

这位后端工程师判断一个算法是否可行单凭直觉,这样的判断肯定是不可取的,正确的判断方式是通过时间复杂度空间复杂度

认识时间复杂度

  • 时间复杂度,定性描述该算法的运行时间,通俗讲就是一个算法的循环次数。

  • 时间复杂度的表示用一个函数 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 来实现栈的功能,通过方法pushpop来实现入栈和出栈。

  • 队列(Queue):一个先进先出的数据结构,JavaScript 中没有队列,通过 Array 来实现队列的功能,通过方法pushshift来实现入队(enqueue)和出队(dequeue)。

  • 链表(LinkedList):一个由多个元素组成的列表,元素存储是不连续,通过next指针连在一起,JavaScript 中没有链表,通过 Object 来实现链表的功能。

  • 集合(Set):一个无序唯一的数据结构,ES6 中的集合, 名Set

  • 字典(Map):一个用键值对存储唯一值的数据结构,ES6 中的字典,名Map

  • 树(Tree):一种分层数据的抽象模型,JavaScript 中没有树,通过 Array 和 Object 构建树。

  • 图(graph):一种网络结构的抽象模型,是一组由边连接的节点,JavaScript 中没有图,通过 Array 和 Object 构建图。

  • 堆(Heap):一种特殊的完全二叉树,所有的节点大于等于(最大堆)或小于等于(最小堆)它的子节点,JavaScript 中没有堆,通过 Array 表示堆。

认识常见算法

  • 链表的遍历、删除链表节点

  • 树和图的深度/广度优先遍历

  • 搜索排序

    • 冒泡排序
    • 选择排序
    • 插入排序
    • 归并排序
    • 快速排序
    • 顺序搜索
    • 二分搜索

认识常见算法设计思想

  • 分而治之
  • 动态规划
  • 贪心算法
  • 回溯算法

最后,希望读者可以通过本篇文章对数据与结构有一定的认识和觉悟。。。。。。