我最近在树上遇到了 DSU 及其应用程序。当我在解决相关问题时，我遇到了 Time Limit Exceeded 错误，所以我再次阅读了教程，在那里我发现普通联合的即兴版本是加权联合. 在这个加权联合操作中，我们将较小子集的根作为较大子集（在两者中）根的子节点。它如何使我们受益？链接到教程
问问题
70 次
2 回答
0
您应该意识到加权联合查找背后的目的/逻辑。
首先，为什么我们需要加权并集查找？那是因为一个简单的低效联合查找会导致不平衡的树。在最坏的情况下投一个链表。遍历链表的复杂度是多少？O(N). 这是使用简单联合查找时最糟糕的复杂性。
我们的目标是——平衡由此形成的树。
加权联合查找如何以及为何起作用？这是一个简单的优化，只需保持每个子集的大小，并在两者之间执行联合时使较小的子集成为较大子集的子集。
为什么这行得通？因为，如前所述，我们的目标是在进行并集时平衡树，而不是使其不平衡。如果您使较小的子集成为较大子集的子集，则整个树的高度不会增加（当大小相等时，我们会以不同的方式处理它：/）。另一方面，如果您将较大的子集作为较小树的子集，您就知道会发生什么。
仅使用此优化，我们将最坏情况的时间复杂度从O(N)to提高到O(log2(N))- 因为树的高度永远不会超过log2(N)
可以同时进行另一项优化，这将进一步降低复杂性。您的链接可能有它。
于 2020-04-20T19:32:32.537 回答
0
对正确性的观点没有影响，但通常更快。
检查这个例子：
在第一种情况下，您将最大的集合作为最小集合的子集。可以看到，在这种情况下，如果你在最深的节点尝试find方法，它将执行 3 个步骤。在第二种情况下不会发生这种情况。
这不是一个规则，但实际上它就是发生的事情。
于 2020-04-20T19:32:42.440 回答