非不相交集合并集的最佳算法是什么? [英] Whats the best algorithm for Non Disjoint Set Union?

问题描述

让我们说有两个(非不相交)点集(笛卡尔空间)，执行两个集的并集的最佳情况复杂度算法是什么?

Lets say there are two (non disjoint) sets of points (cartesian space), what is the best case complexity algorithm to perform the union of the two sets ?

推荐答案

由于点坐标是任意的，并且它们之间没有特殊关系，因此我不认为此问题是特定于几何的问题.有效地将S1和S2合并为新集合S是普遍的问题.

Since the point coordinates are arbitrary and there is no special relation between them, I don't see this problem as a geometric specific problem. It is the generic problem of efficiently merging S1 and S2 into a new set S.

我知道两种选择:

1)当集合存储在哈希表中(实际上是哈希集)，则联合将O(| S1 | + | S2 |)取为平均值.

1) When the sets are stored in a hash table (actually a hash set), the union takes O(|S1|+|S2|) in average.

2)如果将结构存储在平衡搜索树中，则可以假设| S1 |> | S2 |，则达到最坏情况O(| S1 | * Log(| S1 |))的时间.

2) If you store the structures in a balanced search tree, you can achieve a worst case time of O(|S1| * Log(|S1|)), assuming that |S1|>|S2|.

这篇关于非不相交集合并集的最佳算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！