如果我有 n 个单节点树和 m 个查找集合操作(注意:没有并集，假设之前已经完成并集)并且只使用路径压缩，这真的需要 O(m) 时间吗？我一直试图证明这一点，但似乎并非如此。由于并集没有按等级使用并集，因此查找集最多可能需要 O(n) 时间。但是是否仍然有可能在 O(m) 时间内完成 m 个查找集？
最佳答案
这通常不会花费 O(m) 的时间来完成。想象一下，n 个节点被分成 √n 个组，并且在每个组内，所有节点都链接在一起形成一个大小为 √n 的链表。现在，如果您进行 √n 次查找操作，每个链表的根一个，完成的总工作量将为 Θ(n)，因为您必须更新组中几乎每个节点上的指针。
但是，如果您以不同的顺序执行查找操作(例如，从链表的末尾开始并向后工作)，您可以在 O(n) 时间内完成 n 次操作。
一般来说，the cost of union-find using only path compressions is O(m log n + n) for m operations on n nodes .
关于algorithm - 查找具有路径压缩而不按等级并集的集合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36144470/