# 数据结构与算法

数据结构和算法是程序员的基本功,值得每一个程序员好好学习。数据结构表示计算机存储数据的方式,算法是完成某个特定任务的过程。

  • 数据结构
  • 算法
  • 前端中的数据结构和算法

# 数据结构

在计算机科学中,数据结构(data structure)是计算机中存储、组织数据的方式。通常我们可以从逻辑结构存储结构这两个维度进行分类。

# 按逻辑结构分类

反映数据元素之间的逻辑关系。

  • 集合(无逻辑关系)
  • 线性结构(线性表)
    • 一维数组。
    • 队列。
    • 栈。
  • 非线性结构。
    • 树。
    • 图。
    • 多维数组。

# 按存储结构分类

数据结构在计算机中的表示,是按照真实的物理地址分类。

  • 顺序存储结构
    • 数组。
  • 链式存储结构。
    • 链表。
  • 索引存储结构。(增加了附加的索引表,来确定结点存储地址)
    • 数据库索引
  • 散列存储结构。(将索引存储结构中的索引存到了数据内,即直接根据数据就能找到存储地址)

存储结构分类

# 算法

算法(algorithm),在数学和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。

# 算法分类

算法可以分为以下几类:

  • 分治法
    • 递归,将大问题分解成子问题(子问题相互独立,且与原问题相同)、将子问题合并成原问题的解。
  • 动态规划法
    • 递归,记录已解决的子问题的答案,根据子问题求解原问题的解(子问题不独立)。
  • 贪心法
    • 局部最优,根据当前信息做选择。
  • 回溯法
    • 通用的解题法,解空间树(深度优先遍历),找出满足条件的所有解。
  • 分支界限法
    • 解空间(广度优先、最小耗费优先)、界限函数(队列式、优先队列式)。
  • 概率算法
    • 随机性选择,小概率错误(运行时间大幅减少),对同一问题求解两次,可能得到完全不同的解,且所需时间、结果可能会有相当大的差别。
  • 近似算法
    • 求近似解,定义容错界。

算法分类

# 时间复杂度和空间复杂度

我们常常用时间复杂度和空间复杂度来衡量一个算法的效率。

时间复杂度:描述了该算法的运行时间。一个算法的质量优劣将影响到算法乃至程序的效率。

常用的时间复杂度:

  • O(1),哈希查找。
  • O(n),单层循环。
  • O(lgn),二分法。将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推。
  • O(nlgn),归并排序。将一个数据集分成两半,然后将分开的每一半再分成两半,依此类推,在此过程中同时遍历每一半数据。
  • O(n²),双重循环。
  • O(n³),三层循环。
  • O(2^n),穷举查找,检查所有子集。
  • O(n!),菲波那切数列。

空间复杂度:对一个算法在运行过程中临时占用存储空间大小的量度。

# 算法解题思路

当我们在遇到一个算法的问题时,可以按照以下步骤进行思考,避免走弯路。

  • 枚举法:先不考虑算法复杂度,先用枚举法(暴力法)完成需求。
  • 想办法优化,例如猜生日算法:
    • 穷举法,从 1 月 1 日开始比对,比对到 12 月 31 日。要比对 366 次。
    • 优化 1:先比对 12 次月份,确定完月份,再比对日期,最多要比对 12 + 31 次。
    • 优化 2:使用二分法,先比对 6 月是大是小,确认完月份以后,再用同样的方法比对日期。
  • 递归算法
    • 化繁为简:将一个大事情,分解成 1 步 1 步的小事情。
    • 分而治之:把问题分成多个模块,一块一块的解决。
    • 化虚为实:将不明白的业务,转换成我们熟悉的业务,先理清逻辑,然后再替换回去。

# 前端中的数据结构和算法

上文中介绍了很多理论都是计算机底层的东西,接下来我们看一下前端中能够接触到的数据结构和算法。

# 内存栈和内存堆

  • 函数执行的时候会把局部变量压到一个栈里面。
  • 内存里的堆是指存放 new 处来动态创建变量的地方。

栈区(stack):由编译器自动分配释放,存放函数的参数值,局部变量的值等,其操作方式类似于数据结构的栈。

堆区(heap):一般是由程序员分配释放,若程序员不释放的话,程序结束时可能由 OS 回收,值得注意的是它与数据结构的堆是两回事,分配方式倒是类似于数据结构的链表。

全局区(static):也叫静态数据内存空间,存储全局变量和静态变量, 全局变量和静态变量的存储是放一块的,初始化的全局变量和静态变量放一块区域,没有初始化的在相邻的另一块区域,程序结束后由系统释放。

文字常量区:常量字符串就是放在这里,程序结束后由系统释放。

程序代码区:存放函数体的二进制代码。

提示

简单类型的变量存在栈里,引用类型变量存在堆里。

堆内存低位向高位增长,栈内存相反。

# Object 和 Map 比较

我们来分析一下 Object 和 Map 这两种数据结构。

相同点:

  • 都是一种以 key-value 存储数据的结构,我们只要输入 key,即可查找到其对应的值。

不同点:

  • Obejct 的 key 只能是字符串。
  • Map 可以轻松的获取大小,Object 必须手动追踪大小。
  • 存储结构不一样, Object 有一个专门存放 key 和一个存放 value 的数组,如果能找到 key,则拿到这个 key 的 index 去另外一个数组取出 value 值。当发生散列值冲突时,根据当前 的 index,直接计算下一个查找位置。

# 总结

本章只介绍了数据结构和算法的理论,后面会更新更多相关的实战文章来深入学习。