查找具有路径压缩而不按等级并集的集合
Find set with path compression without union by rank
如果我有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。
如果我有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。