假设有两个（非不相交）点集（笛卡尔空间），执行这两个集的并集的最佳情况复杂度算法是什么？
由于点坐标是任意的，并且它们之间没有特殊关系，因此我不认为这个问题是一个几何特定问题。这是有效地将 S1 和 S2 合并成新集合 S 的通用问题。
我知道有两种选择：
1）当集合存储在哈希表 http://en.wikipedia.org/wiki/Hash_tables（实际上是一个哈希集），联合需要 O(|S1|+|S2|)average.
2）如果将结构存储在平衡搜索树 http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree，您可以实现 O(|S1| * Log(|S1|)) 的最坏情况时间，假设 |S1|>|S2|。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
