Algorithm

更关注算法的证明，用起来才安心。

0. 时间复杂度

Harmonic series

\[\sum_{n=1}^\infty\frac{1}{n} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots \approx ln(n) + 0.577\]

证明是发散的

\[1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \cdots \geq 1 + \frac{1}{2} + \frac{1}{\color{red}{\mathbf{4}}} + \frac{1}{4} + \frac{1}{\color{red}{\mathbf{8}}} + \frac{1}{\color{red}{\mathbf{8}}} + \frac{1}{\color{red}{\mathbf{8}}} + \frac{1}{8} + \frac{1}{\color{red}{\mathbf{16}}} + \cdots\]

所以有

\[\sum_{n=1}^{2^k} \frac{1}{n} \geq 1 + \frac{k}{2}\]

1. 图

1.1 最小生成树(MST)

1.1.1 prim算法

随机选一点作为初始点，记为集合\(S\)的初始状态，其余点集合记为\(T\)，每次选择最短的一条边，这条边需要连接 \(S\) 中的一个点和 \(T\) 中一个点，然后将 \(T\) 中的那个点放进 \(S\) ，循环直到 \(T\) 为空。

prim正确性证明:

反证法，假设prim算法生成的树为 \(T\), 实际的某个最小生成树为 \(T'\)， 那么 \(T\) 和 \(T'\) 之间肯定有一条边不一样(不关心长度)，否则树的权重相同(不考虑 \(T\) 和 \(T'\) 权重一样的情况，没有意义)。 记在 \(T\) 中而不在 \(T'\) 中的一条边为 \((u, v)\)，当 \((u, v)\) 这条边被加入 \(T\) 时，它连接了 \(A\) 和 \(B\) 两个集合，且是这两个集合中的最短路径。由于 \(T'\) 也是连通且只有 \(n - 1\) 条边，那么存在一条边 \((x,y)\) ， 去掉它之后将整个图也分成了\(A\) 和 \(B\) 两个集合。根据定义，\((u, v)\) 的权值只会小于等于\((x, y)\)。

• 如果 \((u, v) < (x, y)\)，\(T'\) 将 \((x, y)\)换成\((u, v)\)，权重会更小，与其最小生成树的假设矛盾
• 如果 \((u, v) = (x, y)\)，\(T'\) 将 \((x, y)\)换成\((u, v)\)，权重不变，但是 \(T\) 和 \(T'\) 的不相同的边减少一个，继续这个步骤。最后要么所有边一样，要么进入\((u, v) < (x, y)\) 分支，也得出矛盾。

因此，prim算法生成的生成树就是最小生成树

1.1.2 瓶颈MST

即最大边权最小的生成树

• 定理: 一棵最小生成树必定是一棵最小瓶颈生成树。

证明: 如果一个普通生成树为 \(T\)， 一个瓶颈生成树为 \(T'\)，那么 \(T\) 中有条边比 \(T'\) 中所有边都长，记为\((u, v)\)。同样的，这条边将树分割成\(A\) 和 \(B\) 两个集合。我们也能在 \(T'\) 中找到一条边 \((x, y)\) ，将树分割成\(A\) 和 \(B\) 两个集合。如果我们将 \((x, y)\) 在 \(T\) 中替换 \((u, v)\)，那么 \(T\) 的权重变小，说明 \(T\) 不是MST，与假设矛盾。

1.1.3 Cayley公式

一个完全图，一共有 \(n^{n - 2}\) 个不同的MST，证明比较难，有需要时再更新。

1.1.4 Kruskal算法

先把所有的边排序，从小到大依次尝试加入MST，如果能连接两个连通分量，则将这条边加入MST，因此需要使用并查集。

1.2 最短路

假设图有 \(n\) 个点，\(m\) 条边，且假设没有重边。

1.2.1 Dijkstra算法

不能处理负边，因为每一轮迭代要”commit”一个点的距离，如果有负边，可能需要更新已经commit了的点，与算法实现不符。

比如下面的图

1 ---a--- 2
|       /
|     c 
b    /
|  /
| /
3
如果边a = 10, b = 15, c = -5. 
按照dijkstra算法，第一轮迭代会认为到2的距离是10，但实际上是10+(-5) = 5

如果是普通版本，则时间复杂度为\(n^2\)，适用于稠密图(\(m \approx n^2\) )。

如果为堆优化版本，则时间复杂度为\((m +n)log(m)\) ，适用于边数较少的情况。每条边最多被放进堆一次，所以有 \(m\) 次 \(log(m)\) 复杂度的插入操作 ，每轮迭代会选一个最小值，所以有\(nlog(m)\)

2. 动态规划

2.1 背包问题

大致参考背包九讲，补充一些思考与证明。

2.1.1 多重背包

有 \(N\) 种物品和一个容量为 \(V\) 的背包。第 \(i\) 种物品有 \(M_i\) 件可用，每件物品耗费 \(C_i\) 空间，价值为 \(W_i\) ，求能获得的最多价值。

解法: 如果所有的 \(M_i\) 加起来都不大，可以尝试直接用01背包来做，复杂度 \(O(V \sum M_i)\) 。

另一种优化仍然是用01背包，但不是把 \(M_i\) 件一个个分成 \(M_i\) 个。而是按二进制分 \(1, 2, 2^2...2^{k-1}, M_i - (2^k - 1)\) 个物品，可以证明这 \(k + 1\) 项的和为 \(M_i\) 。因为\(1, 2, 2^2...2^{k-1}\) 每一项选或不选一共可以组成 \([0, 2^k - 1]\) 的所有数，最后加上 \(M_i - (2^k - 1)\)，自然范围就成了 \([0, M_i]\) 。转成这种01背包后的时间复杂度为 \(O(V \sum log(M_i))\)

2.1.2 完全背包

每种物品有无限个。时间复杂度 \(O(NV)\)，和01背包类似，但需要从 \(0\) 到 \(V\) 遍历。01背包逆序是因为只能选一个，因此 \(dp[i][j]\) 必须从 \(dp[i - 1][j - C_i]\) 转移。但是完全背包可以选无限个，直接大容量背包从小容量背包转移来就OK。

但实际上，完全背包也可以倒着算，但是就需要 \(dp[i][j]\) 从 \(dp[i-1][0..(j-1)]\)转移而来，转移方程就不再是 \(O(1)\) 的。为了加速运算，我们直接从 \(dp[i][j - C_i]\) 转移，结果是一样的，这才导致完全背包的遍历方向和01背包不同。

3. 树

3.1 平衡树

3.1.1 红黑树

红黑树有以下性质

• Every node is colored red or black.
• The root node is a black node.
• NIL children count as black nodes.
• Children of a red node are black nodes.
• For all nodes x: all paths from x to NIL’s have the same number of black nodes on them.

**如果一共有 \(n\) 个内部节点(就是不算nil节点)，树高不超过 \(2log(n + 1)\) **

证明:

1. 定义 \(b(x)\) 是节点x到 nil 节点的任一路径的黑色节点数，不包括x自己，但包括nil

2. 那么以 \(x\) 为根节点的子树，至少有 \(2^{b(x)} - 1\) 个节点(不包括nil，包括\(x\) 自己)。可以分类讨论 \(x\) 有几个直接的儿子节点，当有2个时，记为节点a, b，则有\(b(a) \ge b(x) - 1\) 和 \(b(b) \ge b(x) - 1\)，于是根据数学归纳法，\(x\)节点的子树至少有节点 \(2^{b(x) - 1} - 1 + 2^{b(x) - 1} - 1 + 1 = 2^{b(x)} - 1\)，得证。

3. 那么有 \(n \ge 2^{b(root)} - 1\)，根据红节点子节点必为黑的性质，有\(b(root) \ge height / 2\)，于是 \(n \ge 2^{height/2} - 1\)，变换一下就得到 \(height \le 2log(n +1)\) 。

所以，红黑树的查询一定是 \(log(N)\) 的，插入和删除也是基于搜索的，也是 \(log(N)\)，和AVL树相同。但是，AVL树的平衡更严格，也就是更”扁”，所以AVL树的查询性能理论上更好，而红黑树对修改操作性能更好，不过大体上性能不会差异很大。

3.1.2 B-Tree

B-tree和BST很不一样，每个节点可以不止两个子节点，且所有叶子节点在同一层。

一个n阶B树有以下性质

• Every node has at most \(n\) children.

• Every internal node(除开叶节点和根节点) has at least \(⌈n/2⌉\) children.

• The root node has at least two children unless it is a leaf.

• All leaves appear on the same level.

• A non-leaf node with k children contains k−1 keys.

Rust的使用了B Tree，理由是对cache更友好，但确实需要更多的比较。

4. 数学

4.1 康托展开

给定一个$1$ 到 \(n\) 的排列，求出这是从小到大所有排列中的第几个排列，比如\([1, 3, 2]\)是第2个排列，计算方法

\[X = a_1(n-1)! + a_{n-2}(n-2)! + ...+ a_n0!\]

\(0 \le X < n!\) 且 \(0 \le a_i < n\) 这里的\(a_i\)表示第\(i\)个数是所有未出现数中的第\(i\)大的，不是指第\(i\)个数本身。

逆康托展开

给定\(X\)，可以求出对应的排列，由于\(21!\)已经超过long long ，所以一般长度不会超过20.

x. 典中典

x.1 线段问题

给\(n\) 个线段，每个位置在\([start_i, end_i]\)，有一系列问题，往往需要将线段按左端点或右端点排序。

x.1.1 最少几个线段，可以覆盖\([0, target]\) 的所有整数

可以按左端点从小到大排序，然后依次遍历，时间复杂度\(nlog(n)\)，常数空间。

第一个线段一定从\(0\) 开始，记录所有以 \(0\) 作为左端点的线段，最远能到达的距离，记为\(last_1\)，那么第二个线段的左端点一定在\([1, last_1]\)范围内，遍历这些线段，记录最远能到达的右端点是\(last_2\)，那么第三个线段左端点一定又是在\([last_1 + 1, last_2]\) 范围内…直到\(last_i\)超过\(target\)就停止遍历，需要注意边界情况，中途可能发现无法覆盖。

x.1.2 给定所有线段，线段之间不能重复，最多能覆盖多少区域

如果所有线段范围在 \([0, m]\)，且端点可重复。 那么可以设置\(dp[m]\)，枚举以\(j\)为右端点的线段，假设其中一个线段是\([i, j]\)，就有\(dp[j] = max(dp[j-1], dp[i] + (j - i))\)