有什么理论复杂但是实现简单的算法？ 第1页

提名并查集。在《算法导论》中被称为“不相交集合森林”。

没人能否认并查集实现简单（除非毒瘤出题人进行毒瘤扩展），因为其核心函数一行就可以实现。

       int findSet(int x) {     return par[x] == x ? x : par[x] = findSet(par[x]); } // par数组中，par[x]表示结点x的父结点。若x为根结点，par[x] = x。      

但当初学习时并没有深入思考其复杂度，只是简单接受了“近似O(1)”的这个结论。

然而这个复杂度分析比实现要复杂得多。后文主要着眼于复杂度分析，假设读者对并查集有一定了解，至少知道这玩意是啥。

以下需要对并查集有基本的了解。

一.并查集简述（回顾)

并查集是一个森林，由许多棵有根树组成，每棵树都表示一个集合，树的一个结点表示一个元素。这实际上就是并查集的精髓，两个元素所对应的结点在同一棵树中，意味着两个元素在同一个集合中，反之亦然。

而并查集的功能（操作），就如它的名字：合并和查询。

• 合并 unionSet：把森林中的两棵树合并为一棵树，也就是合并两个集合。
• 查询 findSet：查询某个结点所在的树的根结点。通过比较两次查询操作，我们就可以得知两个结点在不在同一棵树中，实际上也就是得知两个元素在不在同一个集合中。

二.实现方式及复杂度分析

并查集有多种实现方式（优化方式），比如按秩合并和路径压缩。上面的代码就采用了路径压缩，相信OIer们都看得懂。findSet函数经过一系列递归，最后的返回值是这棵树的根结点，于是par[x] = findSet(par[x])这句代码就将结点x的父结点标记为树的根，从而实现了路径的压缩。

一步一步来。

以下假设n为总结点数，m为操作数。初始情况下，我们有n棵只有一个结点的树。

1.最朴素的（没人写的）并查集

最朴素的并查集，也就是没有按秩合并，也没有路径压缩。这就导致我们可以构造出一组数据，在n次合并之后得到一个长度为n的链，使得这个并查集的时间复杂度非常高。这其实和二叉查找树（BST）有一点相似，都可以通过构造数据使树退化一条链。为了防止这种退化，BST被改进为平衡二叉树（BBST）；而并查集则通过种种启发式策略进行优化。

如果树退化为链，我们对叶结点进行查询/合并操作，那就需要遍历整个树（链），复杂度达到了 ，高的可怕。

2.按秩合并的并查集

按秩合并，略显晦涩的名字，但它的英文union by rank很容易理解。秩（rank）的定义并不固定，有的人定义树的大小即结点数量（size）为秩，有的人定义树的高度（height）为秩。但无论如何，它们合并操作的思想是一样的，如下：

       void unionSet(x, y) {     x = findSet(x); y = findSet(y); // 找到它们的根     if(rank[x] > rank[y]) par[y] = x;  // 数组rank储存结点的秩，可以是size或者height     else                  par[x] = y;     update(rank, x, y); // 自由发挥啦，是size改size，是height改height }      

我们先分析以高度height为秩的并查集。

• 引理1：以高度height为秩的按秩合并并查集中，每棵树的高度最多为 ，且可达到 （此处及此后均假设 以2为底）

证明：首先显然，被我们合并的两棵树，当且仅当高度相同时，合并后得到的树高度会变化为原高度+1；其余情况，合并得到的树高度与原来两棵树中最高的那棵高度相同。因此，想得到一棵高度为的树，就必须由两棵高度为 合并得到……一直推下去，我们至少需要 个结点才行。而要得到高度为 的树，就需要 个结点。显然 ，证明完毕。

这样，在一系列合并之后，我们就可以使查询操作的最坏情况达到 。

更进一步，我们分析以大小size为秩的并查集。一个显而易见的思路是建立size和height之间的关系，从而间接得到复杂度。

• 定义：
• 引理2：单调性：对任意 ，有 ，这是显然的。
• 推论3：若 是使 的最小的 ，则 是使 的最小的 。用引理2反证可得。
• 推论4： 。数学归纳法，显然 ，由推论3可得推论4。

推到推论4，我们已经得到size和height的关系。

于是有结论：对于按秩合并的并查集，不论以size为秩，还是以height为秩，单次操作最坏情况都是 ，m次操作的总复杂度也就是 .

到这为止，一切都并不很复杂。但一旦涉及到路径压缩，分析的困难就增加了。因为路径压缩有多种启发式策略，其本身还可以和按秩合并结合。这方面的很多成果都由Tarjan先做出来的，其中使用了摊还分析。

正在治疗懒癌，活下来再更新……

Batch Normalization

实现有多简单，标准化+反标准化。

理论有多复杂，到目前为止，都没有很好的理论证明，绝大多数文章还停留在实验阶段。

据我所知，BN的解释经历了这么几个主要阶段：

1. 避免Internal Covariate Shift

原始的BN论文给出的解释是BN可以解决神经网络训练过程中的ICS（Internal Covariate Shift）问题，所谓ICS问题，指的是由于深度网络由很多隐层构成，在训练过程中由于底层网络参数不断变化，导致上层隐层神经元激活值的分布逐渐发生很大的变化和偏移，而这非常不利于有效稳定地训练神经网络。

2. 平滑loss landscape

BN效果好是因为BN的存在会引入mini-batch内其他样本的信息，就会导致预测一个独立样本时，其他样本信息相当于正则项，使得loss曲面变得更加平滑，更容易找到最优解。相当于一次独立样本预测可以看多个样本，学到的特征泛化性更强，更加general。

这个结论在之前的How Does Batch Normalization Help Optimization?文章中明确提出来过。

图中展示了用L-Lipschitz函数来衡量采用和不采用BN进行神经网络训练时两者的区别，可以看出未采用BN的训练过程中，L值波动幅度很大，而采用了BN后的训练过程L值相对比较稳定且值也比较小，尤其是在训练的初期，这个差别更明显。这证明了BN通过参数重整确实起到了平滑损失曲面及梯度的作用。

3. 导致Information Leakage

在最近很火的对比学习中，如果在mini-batch内计算BN统计量，就会导致预测一个独立样本时，会引入其他mini-batch样本的信息，造成信息泄露，骗过模型。

如图所示，当使用random采样的mini-batch统计量时，验证误差会增加，当使用population统计量时，验证误差会随着epoch的增加逐渐增大，导致明显的过拟合，验证了BN信息泄露问题的存在。

即便是在理论如此匮乏的情况下，BN也孕育出了许许多多的变体，比如GN、LN、IN等等。

batch normalization可以说是深度学习时代的black art，或者说是necessary evil。

Reference

[1] Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

[2] How Does Batch Normalization Help Optimization?

[3] Rethinking "Batch" in BatchNorm