1

什么数据结构在时间和空间上都有效地支持以下集合操作？

  1. 联盟
  2. 不同之处
  3. 成员
  4. 添加
  5. 删除

我可以想到 3 种不同的方法来执行这些操作，假设我们有两个集合，它们的大小都是 N：

位数组：

1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)

哈希表：

1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)

有序树：

1. O(NlogN)  2.O(NlogN)  3.O(logN)  4.O(logN)  5.O(logN)

Bit Array 和 HashTable 速度快但占用内存过多，Ordered Tree 速度慢但占用内存少。

请注意：该集合可能包含除整数以外的其他类型，例如浮点数或字符串

还有哪些数据结构既快速又通用，又节省空间？

4

3 回答 3

2

一种选择是使用布隆过滤器来增加有序树，以加快ismemberof类型测试。

我认为整体行为将类似于：

1. O(N log(N) )  2. O( ? )  3.O(1)  4.O(log(N))  5.O( log(N) )

然而，确切的细节将取决于过滤器的大小、集合的大小和域的大小。

另一种选择可能是Judy Arrays。对于这种用途，我听说过关于它们的好消息，但没有个人经验。

另一种选择是福雷斯特方法（而不是纯二叉树）。

于 2012-08-01T06:28:37.060 回答
1

我建议二叉堆（最简单的一个）、二叉堆（加速联合）和斐波那契堆（最难实现，但标准操作的摊销时间最广为人知）。

操作 Binary Heap Binomial Heap Fibonacci heap (amortized)
1. union O(n) O(logn) O(1)
2. Difference O(nlogn) O(nlogn) O(nlogn)
3. find(ismemberof) O(n) O(n) O(n)
4. 添加 O(lgn) O(lgn) O(1)
5. 删除 O(lgn) O(lgn) O(lgn)

但是，这些结构主要用于需要插入、查找/提取 min(max)、联合和删除操作时。find和diff操作的运行时间仍然很差。

于 2012-08-01T18:45:36.870 回答
0

您还可以查看联合查找数据结构

于 2012-08-05T08:50:19.317 回答