计算机技术学习札记

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

2024 年 11 月 2 日

第 2 讲：复杂度的阶 #

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

image​

第 4 讲：哈希 #

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

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

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

删除 #

  • 无孩子：直接删除；

  • 有一个孩子：直接跳过；

    image​

  • 有两个孩子：找到它的后继（或者前驱）然后交换。

    • 有右子树：后继是右子树的最左结点。
    • 无右子树：后继是它最小的祖先，其左孩子也是它的祖先。

第 6 讲：红黑树 #

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

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

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

插入 #

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

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

    image​

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

    image​

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

    image​

第 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：

image​

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

image​

删除 #

（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’’)$。

于是变为

image​

松弛型 #

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

image​

单纯形法 #

  1. 观察 Z，找到对它增长最大的元素（$x_3$）

  2. 观察 $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 $$

  3. 代入，重复。

第 14 讲：FFT #

没看懂，呜呜

第 15 讲：问题的困难性 #

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

image​