我不明白为什么带有列表的不相交集合的加权并集的复杂度对于一个并集来说是 O(log n) ，对于 n 个并集来说是 O(nlogn) 。
我知道复杂性取决于我们必须调整指向集合代表的指针的元素数量。 对于加权联合，我的意思是联盟将最短的列表附加到最长的列表，因此我们永远不会遇到将包含 n 个元素的列表附加到较短的列表的情况。
我试图画出最坏的可能情况，即 n 个联合中的每一个列表的长度都是相同的，但我陷入困境，只是没有得到 O(log n)，例如，如果我附加一个一个元素的列表到另一个元素的列表，然后两个元素的列表到另一个元素的列表，四个元素的列表到另一个元素的四个元素，我知道在附加 4 或 8 个元素的列表时，我必须更改 4 或8 个指针，而不是 log(8) = 3 或 log(16)= 4 个指针。
附加 4 或 8 个元素的列表时，我必须更改 4 或 8 个指针
工会不是这样进行的。首先，并集运算不适用于列表，而是适用于树。其次，并集运算采用两个元素，对于这两个元素，不相交集数据结构已在其各自的树中注册了与其各自父代的父关系。然后从这两个树节点遍历到各自树的根。这需要 𝑑 步骤，其中 𝑑 是相应树中节点的深度。不相交集保证这个 𝑑 是 O(log𝑛)，因此找到各自的根是一个 O(log𝑛) 操作。下一个操作是使这两个根之一成为另一个的子根，这样您现在就已经将两棵树合并为一棵树。这是一个 O(1) 操作，所以总共的操作是 O(log𝑛)。
所以在你的例子中，4个指针被更新是不正确的。仅更新一个指针，其他指针间接指向同一根（通过父路径）。