《高级算法设计与分析》光速复习

第 2 讲：复杂度的阶

\(A\) is \(O, o, \Omega, \omega, \Theta\) of B?

第 4 讲：哈希

装填因子 \(\alpha=\frac{n}{m}\)，\(m\) 是槽的个数，\(n\) 是装填了元素的个数。

查找和插入操作的期望探测次数 \(\frac{1}{1-\alpha}\)。

第 5 讲：二叉搜索树（BST）

删除

无孩子：直接删除；
有一个孩子：直接跳过；
有两个孩子：找到它的后继（或者前驱）然后交换。
- 有右子树：后继是右子树的最左结点。
- 无右子树：后继是它最小的祖先，其左孩子也是它的祖先。

第 6 讲：红黑树

红黑树是满足如下性质的 BST，这些性质能保证它的高度在 \(O(\lg n)\)。

根结点是黑色的。
叶结点（NULL）是黑色的。
红色结点的子结点都是黑色的。
对于每个结点，从它到所有后代叶结点的路径上，黑色结点的个数都相同。这个个数称为「黑高」。

有 \(n\) 个内部结点红黑树的高度不会超过 \(2\lg(n+1)\)。

插入

先按 BST 的方法插入，并且把被插入的结点染成红色。这样只有可能破坏上述性质 3。

Case 1：新结点的叔结点是红色的，将父结点、叔结点染黑，然后祖父结点染红。如果祖父结点是根结点就不动它。

Case 3：新结点的叔结点是黑色的，新结点本身是左子结点，右旋。

Case 2：新结点的叔结点是黑色的，新结点本身是右子结点，先左旋转换为 Case 3。

第 7 讲：B 树

定义 B 树的最小度 \(t\)（\(t\geqslant 2\)）：

至少 \((t-1)\) 个关键字，至多 \((2t-1)\) 个
至多 \(2t\) 个孩子

于是 \(t=2\) 的树，每个结点可以有 2、3、4 个孩子，称为 2-3-4 树。

结点分裂

当结点有 \((2t-1)\) 个关键字时，结点可以被分裂成两个有 \((t-1)\) 关键字的结点。例如，\(t=2\) 时：

+---+---+---+        +---+    +---+
| A | B | C |   ==>  | A |    | C |  (B 在上面)
+---+---+---+        +---+    +---+
V   V   V   V        V   V    V   V

注意 \((2t-1)\) 本身是可以稳定存在的最大情况，分裂只会在插入时发生（见下）。

插入

如果待插入的结点本身已经 \((2t-1)\) 了，就要先把它分裂。例如 \(t=3\) 的 B 树如下，插入 Q：

因为结点 RSTUV 已经到 \((2t-1)\) 了，于是先把它分裂，然后再找地方插入 Q。

删除

（TBF）

第 8 讲：增强数据结构

第 13 讲：线性规划的单纯形法

例如，要最小化：

\[-2x_1+3x_2\]

满足

\[\begin{aligned} & x_1+x_2=7 \\ & x_1-2x_2\leqslant 4 \\ & x_1\geqslant 0 \end{aligned}\]

标准型

目标是最大化：将目标式取负得到 \(2x_1-3x_2\)
所有式子都是小于等于：将等式转换为两个式子，将大于等于式取负
有的变量没有非负约束：拆为两个非负变量 \(x'\) 和 \(x''\) 并替换为 \((x'-x'')\)。

于是变为

松弛型

目标还是最大化
用一系列新的变量代替原来的每个约束式，这些变量非负。

单纯形法

观察 Z，找到对它增长最大的元素（\(x_3\)）
观察 \(x_4\) 至 \(x_6\)，看哪个式子对 \(x_3\) 限制得最大。\(x_6\) 只允许 \(x_3\) 增长到 2，用它替换 \(x1\)：
\[x_3=2-\frac{1}2x_1+x_2-\frac{1}2x_6 \]
代入，重复。

第 14 讲：FFT

没看懂，呜呜

第 15 讲：问题的困难性

P：可以在多项式时间内解决。
NP：可以在多项式时间内验证。
NP-Hard：比所有 NP 问题还难，可以由所有 NP 问题归约
NP-Complete：NP 且 NP-Hard

计算机技术学习札记