我已经一天一夜没睡觉了。
这几天在练习并查集。用并查集解题，其实并不复杂。从实用的角度看，会解题就够了。
但是我的强迫症发作了。基于不相交森林实现的并查集，有很多种处理方式：不做任何优化、只按秩合并、只按集合大小合并、只路径压缩（两步法、一步法）、多种优化一起上……这些不同的处理方式，时间复杂度是不同的。
我发现 leetcode 很多涉及并查集的题目的官解，分析复杂度时要不一笔带过，要不胡说八道，而且经常不按秩合并，还声称平均复杂度和按秩合并是一样的。
这让我真的无法忍，我特别想彻底搞清楚各种处理的复杂度上界和下界。
《算法导论》第三版和第四版，都是只给出了最优情况下并查集复杂度的上界的证明，没有论述下界；单一优化时的复杂度，也是一笔带过。这太令人发狂了。另两本经典算法教材，《算法》(第四版)根本没有论述复杂度，《数据结构与算法分析》（第二版），只论述了一个不紧确的上界 ，并且说了句“对它的分析是本书最复杂的分析工作”。
为了彻底搞清楚原委，按照《算法导论》中列出的参考文献，我找到了Tarjan大佬的原始论文。Tarjan大佬是并查集分析领域贡献最大的，也是最早证明其复杂度下界的人。
然后我的噩梦来了。第一次发现，计算机论文读起来有多可怕。不仅本身难以理解，而且不同的教材和论文，论述时用的符号和工具，都有差别，比如 阿克曼函数，在不同的文献里有不同的版本；再比如，m、n 这两个符号，不同文献里的含义是不一样的。
这位图领奖大佬依然健在。如果有一天能有幸遇到他，我一定要问一下他，42 年前，他是如何想到用那个可怕的阿克曼函数来证明并查集复杂度下界的。
我已经因此而一天一夜没睡觉了，当然是看的似懂非懂，惨烈失败了。我感觉我快要挂了。我知道我是活该，我也好想克服这该死的强迫症。毕竟我是来刷题的，不是来搞文献研究的……
