迭代

• 自下而上的解决问题

递归

• 自上而下的解决问题，不断的拆分问题，分治思想。
• 空间复杂度高
• 会产生额外开销，时间效率低。
• 求和操作是在“归”的过程中执行的，每层返回后都要再执行一次求和操作。
• 从数据结构角度看，递归天然适合处理链表、树、图的相关问题，因为它们非常适合分治思想进行拆分。

尾递归

• 函数在返回前的最后一步才进行递归调用
• 可以被编译器或解释器优化，使其在空间效率上与迭代相当。
• 求和操作是在“递”的过程中执行的，“归”的过程只需层层返回。

/* 尾递归 */
function tailRecur(n, res) {
    // 终止条件
    if (n === 0) return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

时间复杂度

• 统计算法运行时间随数据量变大时的增长趋势
• O表示函数的渐近上界。
• O(1)常数阶
• O(n!)阶乘阶
• 最佳时间复杂度Ω欧米茄，渐近下界。

空间复杂度

• 输入空间
• 暂存空间
  • 暂存数据
  • 栈帧空间
  • 指令空间（通常忽略不计）
• 输出空间
• 通常统计暂存数据、栈帧空间、输出空间
• 数组链表线性阶，矩阵、图是平方阶、树是指数阶

数据结构

• 数组是连续空间存储
• 链表是分散空间存储
• 所有数据结构都是基于数组、链表或者二者的组合实现的。
• 基于数组实现的数据结构也被称为“静态数据结构”
• 基于链表实现的数据结构被称为“动态数据结构”

整数编码

• 数字是以补码的形式存储在计算机中的。
  • 原因是带有符号位的负数原码不能直接用于运算。所以都是在反码的基础上进行运算，再转化回原码。
  • 数字0的原码有两种表示方式，会有歧义。但是补码由于进位舍弃也会为00000000。
  • 计算机可以用同样的电路和操作来处理正数和负数的加法，不需要设计特殊的硬件电路来处理减法。
• 正数的反补码与原码相同。负数的反码是除符号位取反，补码是反码+1。
• 正数类型负数比正数多一个例如[-128, -127]
  • 10000000没有对应的原码，所以约定为-128，因为-1+-127的结果就是-128。

浮点数编码 --TODO

字符编码

• 为了计算机表示字符。
• ASCII字符集，128个不同字符，一个字节的低7位，仅能表示英文。
• EASCII字符集，256个不同字符，适应不同语言需求。
• GBK字符集，汉字需求，一个字符占用两个字节。
• Unicode字符集（统一字符编码），为了解决字符集不统一导致乱码的问题，常用字符占用两个字节，生僻字符占3字节，但是每个字符不等长，未解决如何存储和解析的问题。
• UTF-8编码，可变长的Unicode编码方法，使用1-4个字节表示一个字符。
  • UFT-8编码可以向下兼容ASCII码。
  • 前128个码点就是ASCII码，最高位为0。
  • 长度为n字节的字符，首个字节的高n位都设置为1，第n+1位设置为0，从第二个字节开始，将每个字节的高2位都设置为10；其余所有位用于填充字符的Unicode码点。
  • UTF-16编码非英文字符会更加高效。
  • 编码语言的字符编码方案一般采用UTF-16、UTF-32。因为等长字符好处理。
  • 文件存储和网络传输一般使用UTF-8编码

数组和链表

• 索引的本质是内存地址的偏移量。
• 数组优点
  • 空间效率高
  • 支持随机访问
  • 缓存局部性，访问数组元素，还会缓存其周围的其他数据。
• 数组的和删除操作缺点
  • 插入、删除时间复杂度高
  • 插入会丢失元素
  • 删除会内存浪费
• 扩容数组一般是创建一个更大的数组，然后把原数组元素依次拷贝到新数组。
• 链表缺点
  • 访问、查找节点效率低
  • 同数据量更占用内存空间
• 链表优点：
  • 分散空间
  • 插入、删除时间复杂度低
• 单向链表、环形链表、双向链表
• 列表（动态数组）（Q：js如何实现动态数组）
• 内存效率
  • 链表容易数据碎片化
• 缓存效率
  • 缓存行，不仅缓存单个字节，而是以缓存行为单位。
  • 预取机制：尝试预测数据访问模式，提前将数据加载至缓存。
  • 空间局部性，被访问数据附近的数据也会被加载。
  • 时间局部性：数据会被再次访问
  • 数组具有更高的缓存命中率

栈和队列

• 链和数组实现栈的对比
  • 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
  • 基于数组实现的栈可能造成一定的空间浪费。
  • 基于链表实现的栈可以提供更加稳定的效率表现，但会修改指针，影响效率。
  • 链表节点占用的空间相对较大。
• 链和数组实现队列的对比
  • 首尾下标标记、环形数组、取余实现。
  • 其余跟栈类似。
• 双向队列
  • 兼具栈和队列的逻辑

哈希表（散列表）

• 数组的实现
  • 通过hash算法将key转化为hash值，将hash值对桶数量取模，从而获取该key对应的数组索引index。
  • 哈希冲突，多个输入对应一个输出，可以通过扩容哈希表来减少哈希冲突。
  • 负载因子：哈希表元素数量除以桶数量，用来衡量哈希冲突的严重程度。
  • 解决hash冲突
    • 链式地址：
      • 每个数组存的链表头节点。
      • 占用空间大
      • 查询效率降低
    • 开放寻址
      • 线性探测：若发现哈希冲突，则使用相同步长向后线性遍历，直到找到对应元素，插入同理。
        • 容易产生聚集现象，连续位置发生哈希冲突的可能性增大导致恶性循环，影响效率。
        • 不能直接删除元素，只能懒删除，利用常量TOMBSTONE来标记这个桶，也会影响效率。
        • 可以通过每次查询时调换查询元素和TOMBSTONE的位置优化查询效率。
      • 平方探测
        • 跳过探测次数的平方的步数。
        • 问题依然存在，而且可能探测不到整个哈希表。
      • 多次哈希
        • 对key进行多次hash计算。

哈希算法

• 对质数取模，达到哈希值分布均匀，
• 标准哈希算法：MD5、SHA-1、SHA-2、SHA-3，可以将任意长度的输入数据映射到恒定长度的哈希值。
• MD5，SHA-1被多次成功攻击。
• 对象的哈希值通常是基于内存地址生成的。

二叉树

• 常用术语

  • 「根节点 root node」：位于二叉树顶层的节点，没有父节点。
  • 「叶节点 leaf node」：没有子节点的节点，其两个指针均指向。
  • 「边 edge」：连接两个节点的线段，即节点引用（指针）。
  • 节点所在的「层 level」：从顶至底递增，根节点所在层为 1 。
  • 节点的「度 degree」：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
  • 二叉树的「高度 height」：从根节点到最远叶节点所经过的边的数量。
  • 节点的「深度 depth」：从根节点到该节点所经过的边的数量。
  • 节点的「高度 height」：从距离该节点最远的叶节点到该节点所经过的边的数量。

• 二叉树可退化成链表

• 遍历

  • 层序遍历：从上往下，从左往右。（广度优先BFS），通常借助队列实现。
  • 深度优先遍历（DFS）：前序遍历、中序遍历、后序遍历

• 数组表示

  • 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
  • 不需要存储指针，比较节省空间。
  • 允许随机访问节点。
  • 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
  • 增删节点需要通过数组插入与删除操作实现，效率较低。
  • 当二叉树中存在大量None时，数组中包含的节点数据比重较低，空间利用率较低。

• 二叉搜索树

  • 对于根节点，左子树中所有节点的值小于根节点的值小于右子树中所有节点的值。
  • 任意节点的左、右子树也是二叉搜索树，即同样满足条件。
  • 中序遍历是升序的。
  • 查找时间复杂度为O(log n)
  • 常见应用
    • 用作系统中的多级索引，实现高效的查找、插入、删除操作。
    • 作为某些搜索算法的底层数据结构。
    • 用于存储数据流，以保持其有序状态。

• AVL树

  • 既是二叉搜索树、又是二叉平衡树。
  • 在插入和删除节点后，会进行左旋、右旋操作保持平衡。
  • 常见应用
    • 组织和存储大型数据，适用于高频查找、低频增删的场景。
    • 用于构建数据库中的索引系统。
    • 红黑树在许多应用中比 AVL 树更受欢迎。这是因为红黑树的平衡条件相对宽松，在红黑树中插入与删除节点所需的旋转操作相对较少，其节点增删操作的平均效率更高。

• 堆

  • 完全二叉树
  • 常见应用
    • 优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为O(log n)，而建队操作为O(n)，这些操作都非常高效。
    • 堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。然而，我们通常会使用一种更优雅的方式实现堆排序，详见“堆排序”章节。
    • 获取最大的k个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等。

• 选择排序

  • 时间复杂度n的平方
  • 原地排序、稳定性差

  function chooseSort (list) {
    for (let i = 0; i < list.length; i++) {
      let k = i
      for (let j = i + 1; j < list.length; j++) {
        if (list[j] < list[k]) {
          k = j + 1
        }
      }
      [list[i], list[k]] = [list[k], list[i]]
    }
  }

• 冒泡排序
  • 时间复杂度n的平方
  • 原地排序，稳定性好

  function bubbleSort (list) {
    for (let i = 0; i < list.length; i++) {
      for (let j = 0; j < list.length - i - 1; j++) {
        if (list[j] > list[j + 1]) {
          [list[j], list[j + 1]] = [list[j + 1], list[j]]
        }
      }
    }
  }

• 插入排序

  function insertSort (list) {
    for (let i = 1; i < list.length; i++) {
      let temp = list[i]
      let j = i - 1
      while (list[i] < list[j] && j >= 0) {
        list[j + 1] = list[j]
        j--
      }
      list[j + 1] = temp
    }
  }