13

是否存在表示一大组S（64 位）整数的数据结构，它以空开头并支持以下两个操作：

  • insert(s)将数字s插入S;
  • minmod(m)返回最小的数字s。Ss mod m

一个例子：

    插入(11)
    插入(15)
    minmod(7) -> 答案是 15（mod 7 = 1）
    插入物(14)
    minmod(7) -> 答案是 14（mod 7 = 0）
    minmod(10) -> 答案是 11（其中 mod 10 = 1）

我有兴趣最小化花费在一系列n此类操作上的最大总时间。显然可以只为每个操作维护一个元素列表S并遍历它们；minmod然后 insert isO(1)和 minmod is O(|S|)，这将花费O(n^2)时间进行n操作（例如，n/2 insert操作后面的n/2 minmod操作将需要粗略的n^2/4操作）。

O(n^2)那么：是否有可能比一系列操作做得更好n？也许O(n sqrt(n))或O(n log(n))？如果这是可能的，那么我也很想知道是否有数据结构另外允许从 中删除单个元素S，或者删除一个区间内的所有数字。

4

2 回答 2

7

另一个基于平衡二叉搜索树的想法，如Keith的回答。

假设到目前为止所有插入的元素都存储在平衡 BST 中，我们需要计算minmod(m). 将我们的集合S视为数字子集的并集，位于 [ 0,m-1]、[m,2m-1]、[2m,3m-1]等区间内。答案显然在最小数字中我们在每个间隔中都有。因此，我们可以因此查找树以找到该间隔的最小数量。这很容易做到，例如如果我们需要在[a,b]中找到最小值，如果当前值大于a ，我们将向左移动，否则向右移动，跟踪[a,b ] 中的最小值]到目前为止，我们已经见过面了。

现在，如果我们假设m均匀分布在[ 1, 2^64]中，让我们计算我们需要的查询数量的数学期望。

对于[2^63, 2^64-1]中的所有m，我们需要2 个查询。这个概率是1/2。对于[2^62, 2^63-1]中 的所有m，我们需要4 个查询。这个概率是1/4。 ... 数学期望将是sum[ 1/(2^k) * 2^k ]，对于k in [1,64]，即64 个查询。


因此，总而言之，平均 minmod(m)查询复杂度将为O(64*logn)。一般来说，如果我们m有未知的上限，这将是O(logm logn)。众所周知，BST 更新是O(logn) ，因此在n 个查询的情况下的总体复杂度将是O(n logm*logn)。

于 2013-07-24T08:54:32.443 回答
2

部分答案太大而无法发表评论。

假设你实现S为平衡的二叉搜索树。

当你寻找 时S.minmod(m)，你会天真地走树，成本是 O(n^2)。

但是，在步行期间的给定时间，您获得了迄今为止最好（最低）的结果。在以下情况下，您可以使用它来避免检查整个子树：

bestSoFar < leftChild mod m

和

rightChild - leftChild < m - leftChild mod m

如果集合中的数字的公共间距小于 的公共值，这只会有很大帮助m。

第二天早上更新...

Grigor 更好、更全面地表达了我的想法，并展示了它如何适用于“大” m。他还展示了“随机”m通常是如何“大”的，因此效果很好。

Grigor 的算法对于大型企业来说非常有效，m以至于需要考虑小得多的风险m。所以很明显，如果需要，您需要考虑m不同情况的分布和优化。例如，可能值得简单地跟踪非常小的最小模数m。

但是假设m ~ 2^32？然后搜索算法（当然是给定的，但也有其他的）需要检查2^32间隔，这可能相当于搜索整个集合。

于 2013-07-24T06:56:41.697 回答