数据结构与算法

• 算法学习 (opens new window)
• 算法介绍 (opens new window)

时间、空间复杂度

时间复杂度

• 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。
  • 没有循环语句，记作O(1)，也称为常数阶
  • 只有一重循环，则算法的基本操作的执行频度与问题规模n呈线性增大关系，记作O（n），也叫线性阶

常见的时间复杂度

• O(1): Constant Complexity: Constant 常数复杂度
• O(log n): Logarithmic Complexity: 对数复杂度
• O(n): Linear Complexity: 线性时间复杂度
• O(n^2): N square Complexity 平⽅方
• O(n^3): N square Complexity ⽴立⽅方
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

空间复杂度

• 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。
• 一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间

数据结构

数据结构即数据元素相互之间存在的一种和多种特定的关系集合

• 一般从两个维度理解他。 逻辑结构、储存结构

逻辑结构（数据之间的关系）

• 线性结构：
  • 是一个有序数据元素的集合。其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的
  • 常用线性结构：栈、队列、链表、线性表。
• 非线性结构：各个数据元素不再保持在一个线性序列中，每个元素都可能与零个或多个其他元素发生联系。
  • 常用你非线性结构：二维数组、树。

二叉树

二叉树是一种典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

• 用来模拟具有树状结构性质的数据集合

// 创建一个二叉树
class Node {
  // 定义节点
  constructor(data) {
    this.data = data
    this.left = null
    this.right = null
  }
}

const createTree = (arr) => {
  // 创建二叉树
  let tree = new Node(arr[0])
  let Nodes = [tree]
  let i = 1
  for (let node of Nodes) {
    Nodes.push((node.left = new Node(arr[i])))
    i += 1
    if (i == arr.length) return tree
    Nodes.push((node.right = new Node(arr[i])))
    i += 1
    if (i == arr.length) return tree
  }
}

二叉搜索树

二叉搜索树是特殊的二叉树，考察二叉搜索树的题目一般都是考察二叉搜索树的特性，所以掌握好它的特性很重要。

• 若任意节点的左⼦子树不不空，则左⼦子树上所有结点的值均⼩小于它的根结点的值;
• 若任意节点的右⼦子树不不空，则右⼦子树上所有结点的值均⼤大于它的根结点的值;
• 任意节点的左、右⼦子树也分别为⼆二叉查找树。

链表

• 用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

  • 需要遍历才能查询到元素，查询慢。
  • 插入元素只需断开连接重新赋值，插入快。

• 链表在开发中也是经常用到的数据结构，React16的 Fiber Node连接起来形成的Fiber Tree, 就是个单链表结构。

单链表

• 单链表只有next属性

function ListNode(x){
    this.val = x;
    this.next = null;
}

双向链表

• 双向链表添加了prev属性。有了这个属性就可以查到前一个节点了

function ListNode(x){
    this.val = x;
    this.next = null;
    this.prev = null;
}

双指针

双指针的思想在链表和数组中的题目都经常会用到，主要是利用两个或多个不同位置的指针，通过速度和方向的变换解决问题。

• 两个指针从不同位置出发：一个从始端开始，另一个从末端开始；

• 两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

• 对于单链表，因为我们只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的。（通过快慢指针，可以判断一个单链表中是否有环）

栈和队列

• 在数组中，我们可以通过索引随机访问元素。但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构:
  • 栈：先进后出
  • 队列：先进先出

哈希表

• 哈希的基本原理是将给定的键值转换为偏移地址来检索记录。
• 键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。
• 虽然哈希表是一种有效的搜索技术，但是它还有些缺点。两个不同的关键字，由于哈希函数值相同，因而被映射到同一表位置上。该现象称为冲突。发生冲突的两个关键字称为该哈希函数的同义词。

如何设计哈希函数以及如何避免冲突就是哈希表的常见问题。 好的哈希函数的选择有两条标准：

1. 简单并且能够快速计算
2. 能够在址空间中获取键的均匀人分布

堆

• 堆的底层实际上是一个完全二叉树，可以用数组实现
  • 每个的节点元素值不小于其子节点 - 最大堆
  • 每个的节点元素值不大于其子节点 - 最小堆

堆在处理某些特殊场景时可以大大降低代码的时间复杂度，例如在庞大的数据中找到最大的几个数或者最小的几个数，可以借助堆来完成这个过程。

储存结构（逻辑结构用计算机语言的实现）

• 逻辑结构指的是数据间的关系，而存储结构是逻辑结构用计算机语言的实现。常见的存储结构有顺序存储、链式存储、索引存储以及散列存储。
• 例如：
  • 数组在内存中的位置是连续的，它就属于顺序存储。
  • 链表是主动建立数据间的关联关系的，在内存中却不一定是连续的，它属于链式存储。
  • 顺序和逻辑上都不存在顺序关系，但是你可以通过一定的方式去访问它的哈希表，就是数据散列存储。

算法

排序

冒泡排序

循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。下一次循环继续上面的操作，不循环已经排序好的数。

快速排序

选择一个目标值，比目标值小的放左边，比目标值大的放右边，目标值的位置已排好，将左右两侧再进行快排。

归并排序

将大序列二分成小序列，将小序列排序后再将排序后的小序列归并成大序列。

选择排序

每次排序取一个最大或最小的数字放到前面的有序序列中。

插入排序

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

堆排序

创建一个大顶堆，大顶堆的堆顶一定是最大的元素。交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。从后往前以此和第一个元素交换并重新构建，排序完成。

二分查找

二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

递归

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。

• 为了确保递归函数不会导致无限循环，它应具有以下属性：
  • 一个简单的基本案例 —— 能够不使用递归来产生答案的终止方案
  • 一组规则，也称作递推关系，可将所有其他情况拆分到基本案例

数据存储

数组在内存中是怎么存储的？

• 哈希映射或者字典的方式来实现，不是连续的。

JavaScript 引擎已经在为同种数据类型的数组分配连续的存储空间了。优秀的开发者总是保持数组的数据类型一致，这样即时编译器 (JIT) 就能像 C 编译器一样通过计算读取数组了。 如果你在数组里面存储相同类型的元素，JIT会销毁数组重建，（那么在你读取数据的时候，效率会降低），如果存储的元素是同类型的话，Array对象会维护一个真正的数组，在读取效率上大大提升。

什么是真正的数组

• 数组( Array )在内存中用一串连续的区域来存放一些值。注意「连续」一词，它至关重要。