阅读：《算法》

• 基础
• 排序
• 查找
• 图
  • 加权图
• 字符串
  • 正则

基础

• 递归
  • 递归总有一个最简单的情况，即递归结束。
  • 递归调用总是去尝试解决一个规模更小的子问题，至逐渐收敛至最简单的情况。
  • 递归的父问题和尝试解决的子问题之间无交集，可以理解为操作部分不同。
• 数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合
  • 存储结构：顺序存储（数组）、链式（链表）存储等
    • 数组易查不易写（不要被语言实现迷惑了，在 JavaScript 中，是看不到插入操作时，对后续所有元素的移动的）
    • 链表易写不易查（）
  • 逻辑结构：线性结构（栈、队列等）、图、二叉树等

• 算法：一组操作的方式

• 研究抽象数据类型的一个重要类型是控制数据结构的复杂度。

• 数据类型
  • Bag
  • Queue
  • Stack
    • 算术表达式求值应用：妙呀！
  • List
• 算法分析
  • 算法耗时
    • 每条语句的耗时
      • 由计算机性能决定
    • 每条语句的频率
      • 于是频率就成了关键
      • 在一般的频率表达式中一般忽略较小的项，使用~表示，如 N^3/6-N^2/2+N/3，则忽略-N^2/2+N/3
      • g(N)~f(N)表示g(N)/f(N)随着N的增大趋近于1，同时将f(N)成为g(N)增长的数量级
  • 通常的步骤
    1. 确定输入模型，明确问题规模
    2. 识别内循环
    3. 根据内循环中的操作确定成本模型（即算法的基本操作，如常见排序算法内循环中的对数组元素的访问次数）
    4. 判断这些操作的执行频率，确定成本模型的增长数量级
    5. 需要注意的是某些大常数系数、内循环外的大量指令可能对增长造成不可忽略的影响
  • 常见数量级
    • 常数：1
    • 对数：logN
    • 线性：N
    • 线性对数：NlogN
    • 平方：N^2
    • 立方：N^3
    • 指数：a^N
  • 内存评估
    • 略
  • 算法优化
    • 完整而详细的定义问题，找出解决问题所必需的基本抽象操作并定义一份API
    • 简洁的实现
    • 评估实现所能解决的问题的最大规模是否满足预期，是否可改进或另做实现
    • 逐步改进实现，通过经验性分析或数学分析验证改进后的效果
      • 用更高层次的抽象表示数据结构或算法来设计更高级的改进版本
      • 为最坏情况下的性能提供保证时处理普通数据时也要保证普通数据的性能

排序

部分排序实现见 demo

• 二叉树性质：
  • 组合学性质：高度为 h 的最多只可能有 2^h 个叶子结点，拥有 2^h（1* h 个 2） 个结点的树是完美平衡树。
• 归并排序和快速排序的区别
  • 归并排序是局部有序到整体有序。
  • 快拍是整体部分有序（一侧小于基准值，一侧大于基准值）到所有局部部分有序（局部够小时则达到局部完全有序），从而使整体完全有序。
• 堆排序
  • 优先队列：优先队列适用于不需要全部有序的场景下（如只需要知道队列里最高优先级的任务是什么）
    • 基本操作：删除的最大元素、插入元素
  • 堆：
    • 某个结点的值总是不大于（为最大堆）或不小于（为最小堆）其父结点
    • 是一颗完全二叉树
    • 堆的根结点是堆有序的二叉树（都有序的二叉树）
  • 二叉堆数据结构是优先队列的一种实现方式
  • 二叉堆表示法：将堆从上到下，从左到右排进数组（从索引 1 开始），则结点 k 的子结点位置为 2k 和 2k + 1，节点 g 的父结点为 g/2。利用这一特征可以灵活高效实现优先队列
  • 算法：
    • 上浮 swim：结点由下到上进行堆有序化的过程
      • 不停向上交换结点与比他小（最大堆）或比他大（最小堆）的父结点的位置
      • 应用：插入新结点时，可将新结点 push 到数组的最后，与 index/2 比较交换位置
    • 下沉 sink：结点由上到下进行堆有序化的过程
      • 找到所有子节点中比自己大的最大的子节点（最大堆）或比自己小的最小的子节点（最小堆），并与他交换位置
      • 应用：队列根结点剔除后，将最后的结点交换至首位，进行下沉操作使得堆重新有序
  • 利用二叉堆根结点是极值结点（主Key最大或最小的结点）这一特性可以实现排序算法，称之为堆排序算法
    1. 对数据创建二叉树结构（根据表现那条，数组是堆的表现，即二叉树的表现，所以此步有时可以省略）
    2. 使用 sink 循环进行堆有序化（小堆有序后，其父结点再次 sink，则更高一层的堆也会有序，由于叶子结点不需要排序，根据表示法来说，最后一个非叶子结点的索引为 length/2，利用这一推论对堆的有序化可以从倒数第二层开始，即 length/2、lenght/2-1、length/2-2 循环至根结点 1，则二叉树堆有序化完成成为堆）
    3. 将堆的根结点（极值点）提出，对剩余结点组成的失序的二叉树进行重新有序化（参考 sink 的应用），则根结点重新成为极值点
    4. 循环步骤 3 至所有结点都被提出，则排序完成
• 稳定性：
  • 能够保留数组中重复元素的相对位置不变的算法称为稳定的
  • 一般需要排序的元素为复杂数据，有时逻辑处理依赖数据的多个键，以键 A 为标准排序后，再以键 B 排序，可能导致拥有相同键 B 的数据，键 A 顺序混乱，引发额外的使用成本
• 规约：将解决问题 B 的方法来解决问题 A

查找

• 二分查找
  • 链表实现：写快，读慢
  • 数组实现：写慢，读快
  • 树实现：
    • 二叉查找树：左子树比结点小，右子树比结点大
    • 读写速度都居中
    • 糟糕！如果树不够平衡，节点偏重于左子树或右子树的化，性能则无法保证，跟二分查找一样！
• 平衡查找树：为了保证平衡性，出现性能的最差情况！相对于赌运气来说，我们还是求稳定！！
  • 2-3 树：
    • 大致长这样，有两种节点
      • 2节点：节点内有 1 个 key，两条链接，和二叉树一样
      • 3节点：节点内有 2 个 key，三条链接，左链接小于 key1, 中链接在 key1、key2 之间，右链接在 key2 右侧
    • 查找：二叉变三叉的递归，不说了
    • 插入：递归！
      • 2节点：正常插入
      • 3节点：
        • 插入变成4节点（即有三个key）
        • 将 key2 提升（即4结点拆成一个三个2结点的树）进父结点
      • 递归父结点看是不是变成了4节点，继续操作
    • 删除
  • 红黑树：红黑树里节点都是2节点
    • 大致长这样：用一个红色的链接来表示 2-3 树中 3 节点的 key1 和 key2 的关系，即将 2-3 树种的 3 节点想想成用一个特殊红链接连接的两个 2 节点，正常链接为黑链接。这样就消除了树种存在两种节点类型，而是使用一个叫 color 的额外属性来表示节点的特殊性，也正是因为这样，红黑树和 2-3 树是等价的
    • 性质：
      • 任意结点到起任意叶子节点的路径上经过的黑色结点数量相同
    • 查找：红黑树在节点表现上就是个二叉树。
    • 插入：新插入的节点的 color（链接）一律是红的，但是为了维持平衡性我们需要让红链接方向一致且无连续（有与 2-3 的等价性得来，忘了的话，画个 2-3 树，转换成红黑树看看）
      • 消除方向的不一致：旋转
        • 旋转：即交换两个节点的父子关系，从而改变链接方向
        • 左旋转：b(-a,=d(-c,-e))) 变为 d(=b(a,c),-e)，返回链接中新的父节点
        • 右旋转：d(=b(a,c),-e) 变为 b(-a,=d(-c,-e)))，返回链接中新的父节点
      • 消除两个连续红链接：变色
        • 当父结点的两个子节点之间皆为红链接时（旋转或向只有一个红色左链接子节点的节点中插入右节点产生），即等价于4节点，这时要做的是提升中间节点为父结点（参考 2-3 树），在红黑树种表现为，两个子链接变为黑链接，父结点自身的链接变为红链接。
      • 步骤：旋转吧，变色吧，递归直到结束
• 散列表（见算法图解）
  • 无顺序信息，易查
  • 散列表中重要的是散列函数
  • 解决散列碰撞问题：
    • 开发寻址法，当前碰撞则找下一个空位，为保证查询速度，需要不断扩张散列表长度
    • 拉链法：即以链解决碰撞问题

图

• 图实现的数据结构：
  • 邻接表：将每个顶点的所有相邻顶点都保存在该顶点对应元素所指向的一张链表
• 无向图
  • 连通性
• 有向图
  • 可达性
    • 应用：内存管理标记清理的垃圾回收
  • 拓扑排序：所有的有向边都从排在前面的顶点指向后面的顶点，即被指向者在后边
    • 仅适用于无环图
    • 实现使用深度优先的逆后序：递归遍历调用结束后将顶点压入栈
  • 强联通：互相可达
    • Kosaraju 算法
      • 步骤：
        • 求出有向图的反向图
        • 求出反向图的拓扑排序
        • 使用拓扑排序递归顶点
        • 则处在同一递归中的顶点在同一强联通分量中
      • 证明：
        • dfs(G, s) 过程中经过 v，则存在 s -> v，即 s v 联通
        • 则在原图遍历时顶点顺序为 s … v，递归 s 时，v 顶点未被递归（已递归的会被排除）
        • s、… 、v 为反向图的拓扑顺序，由于 s v 联通，则在反向图中 s -> v
        • 反向图中 s -> v 则在原图中 v -> s
        • 则原图中 s -> v，v -> s 同时成立，则 s、v 强联通

加权图

• 最小生成树：一颗含有所有顶点的无环联通子图，树中所有边的权重之和最小
  • 切分定理，将图分为两部分，跨越两部分的所有边中权重最小的边一定在最小生成树中
  • Prim 算法：每条边都是连接当前树和剩下部分的边
    • 步骤：
      1. 将根加入树
      2. 将新加入顶点的边加入列表
      3. 将列表中权重最小的边的另一个顶点加入树（即边加入树），并去除已在树中顶点间的边
      4. 重复2、3
    • 有向图：只需要遍历出边即可
  • kruskal 算法：每条边加入的边都是连接未连接的某两部分的边
    • 步骤：
      1. 将所有边排序
      2. 取列表中权重最小的边
      3. 边加入树中后不会形成环则将边加入树
      4. 重复2、3直到有 v-1 条边
• 最短路径问题
  • 适用：
    • 耗时为 a 的任务可抽象为 a1->a2 权重为 a 的边
    • c 需要在 b 开始后 x 之内开始可抽象为 c -> b 权重为 -x
    • 求解最长路径问题可以对权重取反，此时转化为最短路径问题
    • 含有负权环的问题是不能求解的，需要检测到负权环并跳出
  • 解法：对所有边按照顺序进行“松弛”
    • 步骤：
      1. dist(s -> v) 初始为无穷大（起点到任意顶点为无穷大）
      2. 判断是否 dist(s -> w) > dist(s -> v) + e(v -> w)
      3. 是，则 v -> w 为路径中的一个边，edgeTo[w] = v
    • 狄克斯特拉算法：按照到顶点的权重值大小松弛边
      • 正权边有/无环图
      • 负权边的无环图
    • 拓扑顺序算法：按照顶点拓扑顺序松弛边
      • 无环加权有向图
    • 贝尔曼算法（Bellman-Ford）：
      • 适用：负权边的有环无负环图
      • 实现：
        • 通用：以任意顺序松弛所有边 v 遍
        • 实际：
          1. 以起点 s 开始松弛顶点的出边，并修改 edgeTo
          2. 将所有出边的终点加入队列
          3. 松弛队列中顶点的出边，并修改 edgeTo
          4. 如果到顶点 x 的权重变化，则需要将 x 重新加入队列（因为会影响到其他顶点的权重）
          5. 重复 2、3、4，
          6. 周期性检查 edgeTo 中是否存在负环，存在则中止

字符串

KMP

正则