algorithm - 按等级查找具有路径压缩且没有联合的集合

Question

如果我有 n 个单节点树和 m 个查找集合操作（​​注意：没有联合，假设之前已经完成了联合）并且只使用路径压缩，这真的需要 O(m) 时间吗？我一直试图证明这一点，但似乎并非如此。由于联合没有按等级使用联合，因此查找集可能需要 O(n) 时间。但是仍然有可能在 O(m) 时间内完成 m 查找集吗？

Answer 1

这通常不会花费时间 O(m) 来完成。想象一下，n 个节点被分成了 √n 个组，每个组内的所有节点都链接在一起，形成一个大小为 √n 的链表。现在，如果您执行 √n 查找操作，链表的每个根执行一次，完成的总工作将是 Θ(n)，因为您必须更新组中几乎每个节点上的指针。

但是，如果您要以不同的顺序执行查找操作（例如，从链表的末尾开始并向后工作），您可以在 O(n) 时间内完成 n 个操作。

一般来说，对于 n 个节点上的 m 个操作，仅使用路径压缩的 union-find 的成本是 O(m log n + n)。