0

以下哪种数据结构最适合插入、删除、查找、设置交集、联合？优化时间复杂度。

  1. 位图
  2. 二叉搜索树
4

1 回答 1

3

前进

这个问题是模棱两可的，所以我会做一些假设。

首先，我们试图表示[0 到 M] 范围内的一组数字，其中 M 是一个相当小的数字，例如 100,000。

BST 可以简单地包含集合中的元素。

Bitmap 可以只有 M 位长，如果该位置的数字在集合中，则设置一个位，如果不是，则该数字不在集合中。我假设已经创建了一个大小为 M 的位图。

在这个答案中，我考虑了自平衡二叉搜索树和位图——对于非平衡 BST，您必须处理每个操作的最佳情况、平均情况和最坏情况。

操作和复杂性

插入：将 n 添加到集合中。

  • BST需要 O( log(n) ) 时间进行插入。
  • 位图需要对目标位进行简单的 (OR 1) 运算，并进行快速除法和一些移位以将该 1 放在正确的位置，但仍然保持 O(1)。

删除：从集合中删除 n。

  • BST找到元素，然后删除它，然后旋转树，所以总体 O( log(n) )。
  • 位图需要对目标位进行简单的 (AND 0) 操作，并进行快速除法和一些移位以将该 1 放在正确的位置，但仍然保持 O(1)。

查找：n 在集合中吗？

  • BST需要 O(log(n)) 来查找 n。
  • 位图在特定目标位上返回 (AND 1) 的值，进行除法和移位以将 1 放在正确的位置，总体 O(1)。

Set Intersection：这里有 2 个集合，它们是相同的。

  • BSTs：以一种 MergeSort 样式按顺序遍历两个 BST，如果两个元素相同，则将其添加到返回的 BST 中。

    • 将元素按排序顺序添加到返回的 BST 不利于平衡，因此您可以通过对一半的 BST 进行中序遍历和对后半部分的逆序遍历来修改它，然后添加相交的前向列表和反向列表中的元素以交替顺序排列。
    • 总体而言，这类似于 O( n*log(n) )，因为将所有元素添加到返回 BST 比遍历需要更长的时间。

  • 位图：遍历两个位图，存储字节的（ AND ）（或者说一次 32 位）并将其作为位图存储在结果位置。O( M ) 其中 M 是位图初始化到的范围的大小。

Set Union：这里有 2 套，将它们组合起来。

  • BST：通过在 BST1 和 BST2 之间交替进行 BST1 和 BST2 的广度优先遍历，将 BST1 和 BST2 中的所有元素添加到其中，从而创建一个新的 BST。如果元素已经存在，则不要再次添加它。总的来说，这类似于 O( n * log(n) )。
  • 位图：与设置交集相同，但使用（或）操作。O( M ) 其中 M 是位图范围的大小。

问题中的歧义

  • 这些集合中要存储哪些项目（数字、对象）
  • 要分析的二叉搜索树是自平衡的吗？
  • 这是从相当小的有限范围中选择的集合吗？（即这可以用位图完成吗？）
  • 目前尚不清楚优化时间复杂度的含义，尽管它似乎意味着“对于此数据结构上的此操作的平均情况，已知的最低 Big-O（上限）是多少？”

结论

对于几乎所有这些操作，位图都优于自平衡 BST。

包含/排除位图的缺点：

  • 您只存储包含/排除，并且不存储有关该元素的任何数据。
  • 仅适用于整数，或以 1 对 1 方式散列为整数的对象（如果散列函数是可逆的，您可以将对象取回。）
  • 您必须具有固定范围的元素，例如 0 到 100,000 的整数。
  • 固定范围必须相当小，例如小于 1 亿。
  • 联合和交集取决于范围大小而不是表示的元素数量。
于 2012-07-23T08:30:01.630 回答