是否有可能计算出在分摊的次线性时间内以给定数量为模的一组数的最小值？

Question

是否存在表示大量S(64位)整数的数据结构,这些整数从空开始并支持以下两个操作:

• insert(s)将数字s插入S;
• minmod(m)返回数字s中S,使得s mod m最小.

一个例子:

    insert(11)
    insert(15)
    minmod(7) -> the answer is 15 (which mod 7 = 1)
    insert(14)
    minmod(7) -> the answer is 14 (which mod 7 = 0)
    minmod(10) -> the answer is 11 (which mod 10 = 1)

我有兴趣尽量减少在一系列n此类操作上花费的最长总时间.显然可以只S为每个minmod操作维护一个元素列表并迭代它们; 然后插入is O(1)和minmod 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一个区间内删除单个元素或删除所有数字.

Answer 1

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

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

现在,如果我们假定米的均匀分布在[1,2 ^ 64] ,让我们计算我们需要的查询数的数学期望.

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

因此,总而言之,平均 minmod(m)查询复杂度将为O(64*logn).一般情况下,如果我们中号具有未知上限,这将是O(10gm的logn)时间.如已知的那样,BST更新是O(logn),因此在n个查询的情况下的总体复杂度将是O(n logm*logn).

Answer 2

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

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

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

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

bestSoFar < leftChild mod m

和

rightChild - leftChild < m - leftChild mod m

仅当集合中数字的公共间距小于 的公共值时，这才会有很大帮助m。

第二天一早更新...

格里戈尔更好、更全面地阐述了我的想法，并展示了它如何适用于“大型” m。他还展示了“随机”m通常是“大”的，因此效果很好。

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

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