非不相交集合并集的最佳算法是什么?

本文介绍了非不相交集合并集的最佳算法是什么?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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|.