算法导论笔记（下）

笔记对应的课程为：https://www.bilibili.com/video/av48922404/?p=3 其中本网页包含视频中的11~21集内容。

11. 动态有序统计&区间树

英文：Dynamic Order Statistics & Interval Tree

动态有序统计

功能：
- 返回当前集合的第i小的数
- 返回x在当前集合的排名（Rank)
- 插入操作
- 删除操作（之后忽略不讲。。。）
构造方法：基于红黑树，并在每个节点上多记录一项信息：每个节点所包含的子树的大小（包括其本身）。|我觉得看到这里基本就可以预见如何来编写功能的第1和第2条了。剩下的就是如何在原有的插入和删除操作的更新过程中维护额外的子树大小的信息。

功能1的伪代码，其中x是当前节点，size是子树大小，OS-Select(x, i)是函数名：

 k = size[left[x]] + 1
 if i == k then return x
 if i < k then return OS-Select(left[x], i)
          else return OS-Select(right[x], i - k)

其实在尝试的过程中可以发现上述代码中的k代表了节点x的秩（Rank）。所以功能2的实现就很显然了，通过平衡树的性质快速地找到x，然后直接返回size[left[x]] + 1。

插入的实现：
- 在最开始的确定位置（叶子节点）的过程中，对于每个经过的节点的size进行加一操作
- 再使用红黑树的分类讨论的更新操作，并且你会发现通过保留子树大小而不是直接保留每个节点的秩使得我们在更新操作的时候基本上不需要费心考虑如何维护它。
从动态有序统计总结扩充数据结构功能的一般原则：
- Choose underlying data structure(e.g. red-black tree)
- Determine additional information(e.g. subtree size)
- Verify information can be maintained for modifying operations(e.g Insertion, Delete, Rotation)
- Develop new operations that use info(e.g. OS-Select)

区间树

特点及操作：
- 维护区间的集合，其中每个节点保存一段区间
- 查找给定区间重叠的区间
- 以区间的低端点(low end point)来作为顺序的定义。即左端点小的代表整段区间小。
- 每个节点额外维护的信息是其子树中所包含的所有区间中最大的m。其中m是每个区间的右端点(high end point)的大小。所以$m = max(high[int[x]]], m[left[x]], m[right[x]])$
插入的实现：和DOS差不多，都是在向下确定位置的时候就更新路过的每个节点的m的大小。
Interval-Search(i)的伪代码实现:
```
1
2
3
4
5
6
7
 x = root
 while x != null and (low[i] > high[x] or high[i] < low[x])
 do
     if left[x] != null and low[i] <= m[left[x]]
         then x = left[x]
         else x = right[x]
 return x
```
让我们来解读一下伪代码，其中循环的条件是当前节点x非空，且i表示的区间与当前x所表示的区间没有重叠。（但我有个点没有弄明白，就是重叠的话就直接返回当前的x了，但是x的子树中也有可能包含覆盖i所在的区间。唯一可能的解释是只需要找出其中一个满足的区间即可，但我感觉教授没说，但其实此点很重要）那么先抛开这个疑问不看，继续来看循环中的内容。为什么当low[i] <= m[left[x]]时只需要看左子树呢？这里似乎又印证了我对自己疑问的解释，即当左子树中最大的右端点已经确定比low[i]大了，那么我们要做的就是找到尽量小的左端点来与区间i重叠。这是我自己的理解。

12. 跳跃表

英文：Skip Lists

跳跃表也是维护一个动态有序集合，以很大概率接近O(logN)的时间复杂度找到一个数、插入或删除。其核心是通过多个邻接表来表示一个有序的集合。
教授提了一个非常秀，非常真实的例子：美国纽约地铁。我们也按照相同的顺序来介绍跳跃表。
- 地铁分为两条线：快线和慢线。其中快线之所以快是因为它只包含这条线路的几个站台，如下所示
- 快线：14，，，，，34，，42，，，，，，，，，，，72，，，，
- 慢线：14，，23，，34，，42，，50，，59，，69，，72，，79
- 比如乘客要从14到69，那么最快的应该是快线到72然后往回乘到69。但是程序不会这样往回走，它会直接在快线找到72意识到走过了，然后在快线往回通过42到慢线再往右到达69。所以跳跃表的核心就是通过多建邻接表来节约搜索的时间。
我们先来做一个递推的假设，我们肯定需要一个邻接表记录所有的元素。当我们新建额外的一个邻接表时，如何对它进行设计可以使得搜索的时间复杂度尽量小？
- 直觉告诉我们肯定是平均建站。也就是假设我们建n个快站且总共有N个站，则搜索的时间复杂度约等于$n + \frac{N}{n}$。那么我们很容易地看出或通过求导得出$n = 2 \cdot \sqrt{N} = 2 \cdot N^{\frac{1}{2}}$。
- 但这样的时间复杂度还远远达不到我们想要的，那么我们继续新建线路，通过直觉我们能得出当我们拥有m条线路时，搜索的时间复杂度最优能达到$O(m \cdot N^{\frac{1}{m}}$。那么什么时候能达到每步的操作在lgN级别呢？
- 答案是建立$\log_2 N$条线路，每步的时间复杂度是$2 \cdot \log_2 N$。这时候的跳跃表长什么样呢？
- 1，，，，，，，，，，，，，，，，，，，，9
- 1，，，，，，，，，，5，，，，，，，，，9
- 1，，，，，3，，，，5，，，，，7，，，，9
- 1，，2，，3，，4，，5，，6，，7，，8，，9
- 就像个二叉树。就是维护的地方不太像。。。
搜索操作不用说了，那跳跃表是如何自动维护这么优雅的结构呢？——概率。
- 简单来说，当插入一个元素时，完整的邻接表中肯定是要插入的。然后你开始掷硬币，如果是正面就在上面的邻接表中也添加此元素，直到出现一次反面或所有的邻接表都有了此元素。
- 非常神奇，但是通过严格的证明可以得到这样维护的跳跃表几乎很大的概率都是以lgN的时间复杂度来完成每一次操作的。

13.平摊分析

英文：Amortized Analysis

个人人为本节课比较简单，其主要思想只有一个：将复杂度较高的操作均匀地分配到每次操作中可以使得整体的时间复杂度不会受到较大的影响。
教授从哈希表的扩增说起，比如说表用着用着满了，需要扩增来保持其可用性或保证它的效率。那么就在它满的时候对其扩增。如下所示：
- 1 未满 [1]
- 2 满了，扩增一倍 [1, 2]
- 3 满了，扩增一倍 [1, 2, 3, ] 注意到3后面还有个空位
- 4 未满 [1, 2, 3, 4]
- 5 满了，扩增一倍 [1, 2, 3, 4, 5, , , ] 注意到5后面还有3个空位
- 。。。以此类推
- ——————————我是分割线——————————
- 那么最坏情况下的一步操作是$O(n + 1)$，即包括复制和插入。如果进行n次就会得出扩增会达到$O(n^2)$的时间复杂度。但事实真的如此吗？
- 当然不是，因为只有在2次幂左右时才做了这样的一次操作。所以真正的时间复杂度是$\theta(3 \cdot n)$。
结论：1次或多次的高时间复杂度的操作平摊到每个操作上实际可能是低时间复杂度的操作。
其中记账法(Accounting)和势能法(potential)是用来精确得出平摊后每步的实际操作所消耗的时间。比如扩表的每步操作的花费是3。
但我觉得这不是很重要，也比较简单，而且我也有点困了，就不详细写了。因为我觉得只要能计算出实际的整体时间复杂度就OK了。

14.竞争性分析

英文：Competive Analysis

Self-organizing lists。有n个元素的List（为链表，简称为L）。定义Access(x)为访问x的操作，其花费rank(x)（其等于x距离表头的距离，很好理解，因为链表只能顺序遍历）。同时它还具有交换相邻元素的操作，花费为1。
打住先来看下在线算法和离线算法的区别。在线算法是一次只获得一次操作，并不知道下次操作是什么；而离线算法则预先知道所有之后要执行的操作。所以离线算法的花费肯定是小于在线算法的。而我们打算用在线算法来处理1中的自组织表。
那么在线算法如何保持相对高的效率呢？我们知道假设有些元素的访问频率非常高，那么我们希望它们离表头越近。也就是说理想的排序是按照出现频率的倒序从表头依次存放各个元素。那么当用户访问到一个元素Ele后，我们就不断地交换相邻元素直到把Ele放到表头，也就是说每次我们多花了一倍的代价。（简称为MTF，Move to front）
那么这种启发式算法真的有用吗？这就要介绍本小节的主题：竞争性分析了。其中定义算法$A$具有$\alpha$的竞争性当
$C_{A}(S) \leq \alpha \cdot C_{opt}(S) + k\\ 其中opt为离线算法，也称为上帝算法。可以简单地\\ 认为它知道所有的操作然后选择了最优的处理方式。$
显然$\alpha$越小越好。而MTF算法是最优算法的4倍，其中的证明过程很秀，用到了平摊分析中势能法的内容。hh，我表示没想到，之前没有详细介绍。
所以最优算法并不比MTF算法好多少，这种启发式的思想还被用于操作系统中的内存存取的LRU。学过OS或者计组的同学应该知道。

15.动态规划

英文：Dynamic Programming

贯穿本节的例子是最长公共子序列（Longest Common Subsequence, LCS)。另外本节内容讲的不是很好，主要是由于DP算法不够直观。
最傻最傻的方法是枚举X序列的子序列($O(2^{m})$)，然后在Y序列中验证($O(n)$)。这显然不可行。

那我们一步一步来，首先定义$C[i, j] =

LCS(x[1, …, i], y[1, …, j])

$。也就是说$C$记录了两个序列前缀的最长公共子序列的长度。所以$C[m, n]$就是最终我们需要的结果。

那么我们不难得出如下递推公式：

 //代码并不是这样写的，可以理解为2种情况
 //No.1
 C[i][j] = max(C[i - 1][j], C[i][j - 1]);
 //No.2
 if (x[i] == y[j]) {
     C[i][j] = C[i - 1][j - 1] + 1;
 }

初学者可能需要花些工夫才能理解，画张图啥的就比较清楚了。教授使用了剪贴法证明了其正确性。

总结下动态规划的两个特点（非常重要）：
- Optimal substructure。最优解包含了子问题的最优解。
- Overlapping subproblems。独立的子问题在递归的过程中会被计算多次。
那么简单地使用递归来得到C[i][j]而不保存中间结果（也就是简单地使用上述的伪代码），其算法的时间复杂度还是非常高。那么我们使用Memoization，备忘录算法，开辟额外的空间来记录中间的结果就可以很大程度上缩减算法的时间复杂度。

但动态规划的灵魂是自底向上构建，另外使用循环也使得思路和时间复杂度更加清晰。

 //初始化C[M][N]
 for(int i=1;i<=M;i++) {
     for(int j=1;j<=N;j++) {
         C[i][j] = max(C[i-1][j], C[i][j-1]);
         if(x[i] == y[j])C[i][j] = max(C[i][j], C[i-1][j-1] + 1);
     }
 }
 //C[M][N]就是最终的答案

动态规划的难点是递推式的建立，同时它有非常多的变化问题，也有一些小技巧。比如LCS只需要开两个一维数组就足以记录中间过程。

16.最小生成树

英文：Minimum Spanning Tree(MST)

在此之前你需要了解一些图论的知识。
给定一个有n个点且边有权重的无向图，找到一个生成树（取n-1条边连接n个点），并使得其包含的边的权重最小。
那么首先分析一下这个问题，可以发现它是包含最优子结构特性的，即最小生成树的部分也是局部的最小生成树，这可以通过反证法来得到直观的理解。就是通过去掉其中一条边将最小生成树分为两部分，若是其中一部分有更优的解法，则整体的最小生成树也会有更优的解法，这就导致出现了矛盾。
那么它还满足重叠子问题特性吗？当然满足。比如先移除Edge_1再移除Edge_2，与先移除Edge_2再移除Edge_1得到的状态是相同的三个部分，分别求解最小生成树。所以MST可以用动态规划来求解（但我觉得其实很难建立有效的模型）。但有更加直观和有效率的算法，因为MST满足了贪心算法的特点：局部最优解就是全局最优解。
而目前按照贪心思路来解决MST有两大主流算法：Kruskal和Prim。教授介绍的是Prim算法。但我以前喜欢用Kruskal，感觉更加直观简单。

Prim算法需要写很多东西，这里我就介绍Kruskal吧。首先对边按照权重从小到大排序。然后依次添加进【将原图中的所有边去掉的图】里。如果添加某条边后形成了环路（就不是树了），就略过这条边，直到将n个点全部连接在一起。比较复杂的点应该是如何高效判断是否存在环路，这需要用到并查集的技巧。Kruskal的时间复杂度是$O( E log E )$，也就是主要是排序的过程。