前端日志

# 数据结构与算法

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

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

# 数据结构

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

# 按逻辑结构分类

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

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

# 按存储结构分类

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

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

存储结构分类 (opens new window)

# 算法

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

# 算法分类

算法可以分为以下几类：

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

算法分类 (opens new window)

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

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

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

常用的时间复杂度：

  • 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，直接计算下一个查找位置。

# 总结

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

← 查找算法 →