前置知识

数据结构

  • 数据之间的逻辑关系
    • 集合结构
    • 线性结构
    • 树形结构
    • 图形结构
  • 存储：元素+关系
    • 内容分类：数据，关系，附加（非必要但出于优化的、单数据结构内唯一的内容， 例如长度、根节点…
    • 数据储存方式：顺序，链接
    • 关系算法：哈希，索引，树
  • 接口
    • 构造，销毁
    • 增查删改
    • 访问，遍历

数据结构主要讨论关系的存储

算法复杂度

  • 渐进表示法
    • $O$ : 渐进上界
    • $\Omega$ : 渐进下界
    • $\theta$ : 渐进确界
    • $o$ : 渐近非紧上界

线性结构

线性表

定义：除了首尾元素，每个元素都有其前驱与后继。每个元素对应唯一非负整数 index.

顺序表

struct Vec<T> {
    T* data;
    size_t len, cap;
};
  • 倍增空间：realloc，至多浪费 $50%$ 空间，换取均摊 $O(0)$ 的内存分配（内存分配很耗时）和 $O(1)$ 的复制。
  • 增/删：后继节点全部需要移动， $O(n)$
  • 查：index 访问 $O(1)$，值访问 $O(n)$
  • 遍历：迭代 index: 0..len
  • 优势：局部性好，index 访问快。
  • 劣势：插入、删除、值访问很慢，均摊浪费 $33%$ 空间。
  • 适用情景：静态，可 index 访问。

链表

struct Node<T> {
    T value;
    Node<T>* next; // 若空则 this 为尾节点
    Node<T>* prev; // （双链表专用）指向前面的节点，若为空则是头节点
};
struct LinkedList<T> {
    Node<T>* head; // 可空或伪节点
    Node<T>* tail; // （双链表专用）可空或伪节点
    size_t len; // 可选，长度
};
  • 增删：a->b->c 变成 a->c 并 delete b， $O(1)$
  • 遍历：循环 p<-(p.next)
  • 查：index 与值都是遍历的 $O(n)$
  • 优势：对已知节点增删快
  • 劣势：访问很慢，浪费 1 或 2 个指针的空间

栈

栈：LIFO 后进先出

应用：

  • 函数调用的模拟
    • 递归
    • 深度优先搜索
  • 配对检查
  • 表达式求值（中缀/后缀表达式）

顺序栈

struct Stack<T> {
    T* bottom; // 栈底，不可变
    T* top; // 栈顶，一般取栈顶位置+1，若等于栈底则栈空
    size_t cap; // 容量，用来动态扩容
};
  • push: 把值放在 top 位置并 top 自增，$O(1)$
  • pop: 把 top-1 取出来并 top 自减，$O(1)$
  • 倍增空间同顺序表，均摊 $O(1)$

链接栈

struct StackNode<T> {
    T value;
    StackNode<T>* down; // 指向栈更底下的元素，若空则为栈底
};
struct LinkedStack<T>{
    StackNode<T>* top; // 指向栈顶，若空则栈空
};
  • push: 把值放在新节点里，并把它指向 top，再把 top 设为它，$O(1)$
  • pop：返回 top，并把 top 设为 top.down，$O(1)$

队列

队列：FIFO 先进先出

应用：

  • 列车车厢重排：进入最大可行队尾的队列
  • 模拟排队：先把用户按入队时间排序了，生成队列，再一个个出队

顺序表队列

  • enqueue: insert(len) $O(1)$
  • dequeue: remove(0) $O(n)$
  • peak: visit(0) $O(1)$

循环队列 Circular Queue

优势：内存分配开销少 劣势：内存浪费较多

struct Queue<T>{
    T* base; // 底层数组起始位置
    size_t cap; // 底层数组容量
    T* head; // 队列头
    T* tail; // 队列尾，实际指向尾部+1 的位置，等于头则队列空，等于头 -1 则队列满
};
  • enqueue: *(tail++)=value $O(1)$
  • dequeue: *(head++) $O(1)$
  • peak: *head $O(1)$
  • 注意倍增和取余

链接队列

优势：内存浪费较少 劣势：内存分配开销大

struct QueueNode<T>{
    T value;
    QueueNode<T>* follower;
};
struct LinkedQueue<T>{
    QueueNode<T> *head;
    QueueNode<T> *tail;
};
  • enqueue: tail->next=newnode; tail=newnode; $O(1)$
  • dequeue: node=head; head=head->next; $O(1)$
  • peak: *head $O(1)$

树（数据结构）

定义：有根、除了根每个节点对应唯一父节点的组织结构 要求：无回路，连通 术语

  • 根(root), 叶(leaf), 内部(internal)
  • 子(child), 父(parent), 兄弟(sibling)
  • 祖先(ancestor), 子孙(descendant)
  • 度(degree): 子节点个数
  • 层次/深度(depth): 从根为 1 开始
  • 高(height): 子树最大深度
  • 有序：对于单节点子节点之间有序
  • 森林：一个不相交的树的集合

二叉树

最多两个子节点、左右节点有序的树

  • 满二叉树
  • 完全二叉树：堆式树
  • 完满二叉树：度为 2 的树
  • 数学性质：
    • $n$ 层上最多 $2^{n-1}$ 个节点
    • $n$ 层总共最多 $2^n-1$ 个节点
    • 树枝数 $B=n-1=n_0+n_1+n_2-1=n_1+2n_2$
    • 叶子数 $n_0$ 与二度节点 $n_2$ 有关系 $n_0=n_2+1$
  • 遍历：
    • 前序，中序，后序：深度优先，递归/栈
    • 层次：队列

链接储存

struct BinaryTree<T>{
    BinaryTree<T> *left, *right; // left and right sub-tree/child, null if no child
    T value;
};

堆式储存/顺序储存

// same as vec
struct Heap<T>{
    T* data;
    size_t len, cap;
}
  • 左子: index*2+1；右子: index*2+2
  • 深度优先遍历：递归/循环+switch
  • 广度优先遍历：队列/直接顺序遍历 data（跳过空节点）

哈夫曼树

又称：最优(二叉)树，最小代价树

应用：最佳判定树，哈夫曼编码

树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和 $\text{WPL}=\sum_{i=1}^nw_il_i$

定义：一棵 WPL 值最小的树，是完满二叉树

构造：在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树， 且新的二叉树根结点权值为其左、右子树根结点的权值之和；在 F 中删除这两棵树， 同时将新得到的树加入 F 中：权值小的二叉树作为新二叉树的左子树， 权值大的二叉树作为新二叉树的右子树；在权值相等时，深度小的二叉树作为新二叉树的左子树， 深度大的二叉树作为新二叉树的右子树。

哈夫曼编码：一种可变长(VLC)、前缀编码

前缀编码：字符只放在叶结点中、所以每个字符的编码都不可能是其他字符编码的前缀

树和森林

  • 储存
    • 标准储存：最大度有限，数组储存子
    • 孩子链表：最大度任意，链表存子
    • 孩子兄弟：最大度任意，二叉树左链为树链，右链为兄弟链
    • 双亲表示法：指父
  • 森林储存：本质上是建立一个超级根节点，其他根节点为其子
  • 遍历
    • 只有前序、后序、层次
  • 已知树的前序遍历序列和后序遍历序列，可以确定一棵树（因为子节点集无序）

优先级队列/堆（二叉堆）

定义：满足父节点 op 子节点序关系恒成立的完全二叉树 操作：

  • 向上调整/过滤：while !(父 op 当前) 交换当前与父， $O(\log n)$
  • 向下调整/过滤：while !(当前 op 子x) 交换当前与子x 其中有 子x op 子y， $O(\log n)$
  • 建堆：for i in 1..len/2 向下调整 buf[i] $O(n)$

应用： 愚蠢的 多服务台的排队系统（不看了）

Set and Map

没找到太好的 map 的翻译，先用英文了（

尽管数学上应该先定义 set 再定义 map，但在数据结构这里，由于 set 会唯一对应一个储存 位置，事实上把这个位置拓展出 value 的位置就成了 k-v map 了；因此通常先实现 k-v map， 然后把 set 当作 value 为空的 map（对于不支持零长类型的语言除外）。因此下面只讨论 map。

数据结构中，对于大部分数据结构键在 map 内唯一。

线性 map

最烂的一种结构：线性 map，要么 $O(n)$ 查找 $O(1)$ 插入删除（链表）， 要么 $O(\log n)$ 查找 $O(n)$ 插入删除（有序数组）；更别提都是 $O(n)$ 的无序数组。

对于有序表查找算法我们有

  • 二分查找 $O(\log n)$
  • 插值查找：当 key 分布较为均匀时，可以 $i_{k+1}=low+(\frac{val[i_k]-val[low]}{val[high]-val[low]}(high-low-1))$
  • *分块查找：本质上是双层 B+ 树，因为附带了一个索引。所有操作 $O(\sqrt{n})$

平均查找长度(ASL)：查找次数的加权平均

朴素二叉查找树

定义：满足节点值大于左子树最大值，小于右子树最小值；即中序遍历递增

任意操作时间复杂度 $O(H)$，其中 $H$ 为平均高度。

注意树操作时为了方便最好采用指针引用的方式。

问题：单调数据的插入会造成退化成链表，因此需要插入删除时平衡操作

AVL 树

任何节点的两个子树的高度最大差别为 1。

平衡信息：子树高度。

危机节点：任何节点的两个子树的高度最大差别为1

平衡算法：从底向上，先调整再更新高度，*若都不更新直接返回根节点

旋转操作：见 四种平衡性破坏的情况 | Oi Wiki

缺点：维护代价过大

红黑树，AA 树

本质上是 3/4 阶 B 树，参考 B 树。

Splay 树 / 伸展树

主要想法是，把所有耗时操作都留到读的时候。

主要算法：通过双旋转（which 保证树平衡性不会过度退化），把所有访问过的节点 旋转到根。

缺陷：

  • 读性能较差
  • 由于插入没有做平衡，深度没有保证，容易爆栈

B 树与 B+ 树

不知道为什么教材把他放到 11 章。 真是愚蠢的设计

B 树可以说是组合结构的经典了：它既有数组的连续性，又有链表的灵活性。

定义：

  • 平衡的 M 叉查找树，它仍符合中序遍历单调
  • 任何节点元素个数 $n$ 有 $\lceil M/2\rceil-1\le n\le M-1$，除了根

个人理解：它像是把二叉搜索树的相邻节点中序地“平铺”到了同一层上。

由于 memory cache 和 disk alignment 的存在，现代化处理器对更大块的数据 处理的效率更高，因此 B 树实测性能比传统搜索树都要高，无论是传统的硬盘上还是 近年来流行的内存上。

典型阶数：12 阶（内存型） / 100 阶（外存型）。

阶数选择：一个磁盘块作为 B 树的一个结点效率最高，即 $Block=(M-1)(\texttt{sizeof(K)+sizeof(V)})+M\texttt{sizeof(I)}$

插入：非满数组直接插入，满数组对半分裂

删除：半满数组直接删除，未半满数组“旋转”，借不到合并

B+ 树：

  • KV 只放在最底层，上层只放索引
  • 叶之间双链起来（书上说单链那就单链吧）
  • 有参数最大记录数 L，元素个数 $n$ 有 $\lceil L/2\rceil\le n\le L$
  • 区分内部节点和叶节点

散列表

要求键可哈希。能做到小常数均摊 $O(1)$ 任意操作。

哈希算法

  • 取余
  • 其他根据键分布特性定制的算法（数字分析，平方取中，折叠）
  • 其他通用哈希算法

冲突解决

  • 闭散列：在散列表内寻找空闲位置，很
    • 线性探查：查 $n+i$
    • 二次探查：查 $n+i^2$
    • 再散列：有主、附散列函数 $H_1$ $H_2$，则查 $H_1(x)+H_2(x)i$
  • 开散列：用链表（实际上也可以用小搜索树例如红黑树）

排序

严格来说这算是算法，不知道为啥放在数据结构里。

  • 稳定与非稳定排序

    • 稳定排序：等 key 元素排序后，相对次序保持不变
    • 不稳定排序：等 key 元素排序后，相对次序可能会变

  • 内排序与外排序：

    • 内排序是指被排序的数据元素全部存放在计算机的内存之中，并且在内存中 调整数据元素的相对位置。
    • 外排序是指在排序的过程中，数据元素主要存放在外存储器中，借助于内存 储器逐步调整数据元素之间的相对位置。

  • 比较排序算法

    • 输出顺序的确定依赖于不同元素之间的比较
    • 每次比较能且只能区分一对元素的大小关系
    • 对于输入为 $n$ 的一组元素，其排列顺序的可能性为 $n!$

因此理论上排序算法均摊复杂度不可能小于 $O(\log(n!))=O(n\log(n))$

排序方法 平均 最坏 最好 空间复杂度 稳定性
直接插入排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
希尔排序 $<O(n^2)$ $<O(n^2)$ $<O(n^2)$ $O(1)$ 不稳定
直接选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(1)$ 不稳定
冒泡排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
快速排序 $O(n\log n)$ $O(n^2)$ $O(n\log n)$ $O(\log n)$ 不稳定
归并排序 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $O(n)$ 稳定
基数排序 $O(mn)$ $O(mn)$ $O(mn)$ $O(m)$ 稳定

插入排序

有主循环，每个循环内认为 0..i 是有序的，把 i 号元素上浮

  • 稳定
  • 小常数
  • $O(n^2)$
  • 无额外空间

小优化：二分查找，当比较函数很耗时时有用，否则反而会变慢

希尔排序

按照希尔增量序列分组插入排序。看似是 $O(n^3)$ 实则 $<O(n^2)$

步长序列 最坏时间复杂度
$n/2^{i}$ $O(n^2)$
$2^k-1$ $O(n^{3/2})$
$2^i3^j$ $O(n\log^2n)$
  • 不稳定
  • $O(n\log^2n)$
  • 无额外空间

选择排序

有主循环，每个循环选择最小的放到最前面， $O(n^2)$

  • 稳定
  • $O(n^2)$
  • 无额外空间

堆排序

有主循环，每个循环把堆顶放到最后面，$O(n\log n)$

  • 不稳定
  • 最坏 $O(n\log n)$
  • 无额外空间

冒泡排序

循环i=n-1..-1，从头到 i，有逆序就交换，这样 i..n 就有序了。 一个循环内称为一次起泡（？）。 $O(n^2)$

小优化：当一次循环没发生交换就结束

特点：

  • 稳定性
  • $O(n^2)$
  • 无额外空间

快速排序

通过选定元素划分，通过不断交换 low 与 high 即可实现；然后递归左半边和右半边。 $O(n\log n)$

小优化：

  • 对于小数组采用插入排序
  • 选定随机元素或首、尾、中的中位数

特点：

  • 不稳定
  • 均摊 $O(n\log n)$
  • $O(\log n)$ 栈空间

归并排序

不断二分、合并

  • 稳定
  • 最坏 $O(n\log n)$
  • $O(n)$ 额外空间

桶排序

设有 $k$ 个桶，时间复杂度 $O(N\log\frac N k)$，要求数据分布较为均匀且已知上下限。

需要额外空间 $O(N)$

基数排序

是离散化的桶排序。由于桶内值相同因此相较桶排序不需要桶内排序。

分为 LSD 与 MSD；前者适用于位数少的，后者适用于位数多的（要额外栈空间）

本质上是利用了类似哈希表的有限储存列表，将排序问题转换为遍历列表。

定义基数集合大小为 $B$ ，位数为 $k$ ，考虑到每个元素在每一位上都入桶、出桶各一次， 则有时间复杂度为 $O(k(B+N))$。

由于此过程未作任何比较，尤其适用于长字符串这种比较函数很慢、可基数化的数据排序。

需要额外空间 $O(n)$

外部排序

由于传统外排局限性很大：只能顺序读，甚至不能倒序。因此只能用顺序读的归并排序作为基础， 并做一些优化

置换选择

把有限的内存空间分为两部分：前一部分为小根堆，后一部分为不可入堆元素

对于一个选择片段，不断 pop 最小数，并输入数，若输入小于剩余堆根则放入不可入堆区，否则 push 进堆。

多阶段归并

用斐波那契分割

图

定义： $G(V, E)$ ，其中 $V$ 是顶点集， $E$ 是边集。

由边的性质可分为有向/无向图，有边权/无边权图

术语

  • 图
    • 邻接：由某边连起来的二结点
    • 度：无向图中与某一结点关联的边的总数
    • 入度：有向图中进入某一结点的边数
    • 出度：有向图中离开某一结点的边数
    • 子图：若 $V, E$ 均为子集，则为子图
  • 路径
    • 路径：“一笔画”的边对应的点序列
    • 路径长：无权边数和；有权权和
    • 简单路径：点序列不重复
    • 环：路径节点数不为 1 且首尾节点相同的路径
  • 连通
    • 连通：有路径存在
    • 连通图：任意两点连通的无向图
    • 连通分量：极大连通子图数
    • 强连通：有向图任意两点连通
    • 弱连通图：非强连通，但作为无向图连通
    • 强连通分量：极大强连通子图
  • 完全
    • 完全图：每两个节点之间都有边的无向图称为完全图
    • 有向完全图：每两个节点之间都有双向边的有向图称为有向完全图
  • 有向无环图(DAG)
  • 生成树：连通图的极小连通子图，包含图的所有 $n$ 个结点，但只含图的 $n-1$ 条边

储存

  • 邻接矩阵：A[i][j] 代表从 i 到 j 有一条 A[i][j] 边长的边；边长等于已知 INF 时边不连通
    无向图的邻接矩阵是对称阵
    缺点：内存消耗过大， $\Theta(n^2)$
  • 邻接表：每个点存其出边
    缺点：不好直接检查边存在

遍历：

  • DFS：深度优先，递归/栈
  • BFS：队列

欧拉图

定义

  • 欧拉回路：通过图中每条边恰好一次的回路
  • 欧拉通路：通过图中每条边恰好一次的通路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路但不具有欧拉回路的图

判别：

  1. 无向图是欧拉图当且仅当：
    • 非零度顶点是连通的
    • 顶点的度数都是偶数
  2. 无向图是半欧拉图当且仅当：
    • 非零度顶点是连通的
    • 恰有 2 个奇度顶点
  3. 有向图是欧拉图当且仅当：
    • 非零度顶点是强连通的
    • 每个顶点的入度和出度相等
  4. 有向图是半欧拉图当且仅当：
    • 非零度顶点是弱连通的
    • 至多一个顶点的出度与入度之差为 1
    • 至多一个顶点的入度与出度之差为 1
    • 其他顶点的入度和出度相等

算法：未访问优先的 DFS，访问过的边删掉（无向图）

强连通分量

Kosaraju 算法

第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。（先遍历的编号大）

第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。

评析：主要利用了，强连通图反向后仍强连通的好性质。

拓扑排序

能拓扑排序 等价于 是有向无环图（DAG）；因此判断有向无环可以用拓扑排序

算法：

  1. 从有向图中选取一个没有前驱的顶点，并输出
  2. 从有向图中删去此顶点以及所有以它为尾的边，即它出发的边
  3. 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止

可以维护一个入度表和零入度队列， $O(|E|+|V|)$

AOE 网

AOE 网是一个零入度结点唯一（源点）、零出度节点唯一（汇点）的、带边权的 DAG

关键路径：AOE 网中从源点到汇点的最长路径的长度

关键活动：关键路径上的活动，最早开始时间和最迟开始时间相等

符号定义

  • 对于点 $i$ ，有
    • 最早发生时间 $ee(i)=$ 源点到 $i$ 的最长路径
    • 最晚发生时间 $le(i)=$ $i$ 到汇点的最长路径
  • 边 $v=<j, k>$ ，持续时间是 $L_{jk}$
    • 最早开始时间 $e(v)=ee(j)$
    • 最晚开始时间 $l(v)=le(k)-L_{jk}$

关键路径算法

  1. 利用拓扑排序求出 AOE 网的一个拓扑序列
  2. 从拓扑排序的第一个顶点开始，按拓扑顺序依次计算每个事 件的最早发生时间 $ee(i)$
  3. 从拓扑排序的最后一个顶点开始，按逆拓扑顺序依次计算每 个事件的最晚发生时间 $le(i)$ （注意边要逆向）
  4. 从源点开始遍历出边， $ee(j)=e(v)=l(v)=le(k)-L_{jk}$ 的边即为关键路径一条边，DFS 下去。

（这不求最长路径的 Dijkstra 吗）

专题

外储存器

特点：储存量大，有持久性

运作原理：

  • 寻道：找到对应柱面 （机械硬盘 ~10ms，固态硬盘 0）
  • 定位：找到对应盘面和扇区 （机械硬盘 ~0.2ms，固态硬盘 <0.1ms）
  • 读写：以块为单位读写

因此外储存器

  • 小于块（通常 4kB）大小的数据事实上读写时间是一样的，因此大尺寸数据读写效率高
  • 随机读写需要寻道和定位，很慢；因此随机读写慢，连续读写快

卡特兰数

两种定义：

  1. $C_n= {n\choose 2n}-{n-1\choose2n}$
    • 在 $n×n$ 的网格中，一开始在(0,0)处，每次可以向上走一格或者向右走一格，在任一时刻，向右走的次数不能少于向上走的次数，问有多少种合法路径？（用 $(n,n)$ $(n-1, n+1)$ 映射法）
    • 括号匹配：有 $n$ 个左括号， $n$ 个右括号，有多少种长度为 $2n$ 的括号序列使得所有括号合法？
    • 与 $1, 2, 3,…, n$ 的入栈序列对应的出栈序列种类数
    • 不相交弦问题：一个圆周上有 $2n$ 个点，两两配对并在两点间连一条弦，要求所连的n条弦没有交点，那么一共有多少种配对数？
  2. $C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}$
    • 把一个 $n$ 层的矩形阶梯分为 $n$ 个矩形的方法数？
    • 凸多边形的三角划分：一个凸的 $n+2$ 边形，用 $n-1$ 条直线连接它的两个顶点使之分成n个三角形，每条直线不能相交，问一共有多少种划分方式？
    • 给出某二叉树的先序遍历，该遍历可能对应的二叉树的种类数
    • $n$ 个结点的构成的二叉树种类数