algorithm - 在不相交集联合（DSU）中，为什么我们在执行联合操作时将较小的子集作为较大子集的子集？

我最近在树上遇到了 DSU 及其应用程序。当我在解决相关问题时，我遇到了 Time Limit Exceeded 错误，所以我再次阅读了教程，在那里我发现普通联合的即兴版本是加权联合. 在这个加权联合操作中，我们将较小子集的根作为较大子集（在两者中）根的子节点。它如何使我们受益？链接到教程

标签： algorithmbreadth-first-searchdisjoint-setsdisjoint-union

您应该意识到加权联合查找背后的目的/逻辑。

首先，为什么我们需要加权并集查找？那是因为一个简单的低效联合查找会导致不平衡的树。在最坏的情况下投一个链表。遍历链表的复杂度是多少？O(N). 这是使用简单联合查找时最糟糕的复杂性。

我们的目标是——平衡由此形成的树。

加权联合查找如何以及为何起作用？这是一个简单的优化，只需保持每个子集的大小，并在两者之间执行联合时使较小的子集成为较大子集的子集。

为什么这行得通？因为，如前所述，我们的目标是在进行并集时平衡树，而不是使其不平衡。如果您使较小的子集成为较大子集的子集，则整个树的高度不会增加（当大小相等时，我们会以不同的方式处理它：/）。另一方面，如果您将较大的子集作为较小树的子集，您就知道会发生什么。

仅使用此优化，我们将最坏情况的时间复杂度从O(N)to提高到O(log2(N))- 因为树的高度永远不会超过log2(N)

可以同时进行另一项优化，这将进一步降低复杂性。您的链接可能有它。