今天逛知乎又看到这个问题，决定深入挖掘一下
这两种方法的优势互补，同时使用二者的程序每个操作的平均时间仅为 O(alpha (n)，(alpha (n)是n=f(x)=A(x,x)的反函数，其中 A是急速增加的阿克曼函数。因为alpha (n)是其的反函数，故 alpha (n)在n十分巨大时还是小于5。因此，平均运行时间是一个极小的常数。
实际上，这是渐近最优算法：Fredman和Saks在1989年解释了
Omega ( alpha (n))的平均时间内可以获得任何并查集。[2]
Fredman, M.; Saks, M., The cell probe complexity of dynamic data structures, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, May 1989: 345–354, Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.
int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}
