2

我有一组不相交的整数区间，并想检查给定的整数是否位于其中一个区间内。当然，这可以通过对数时间内的二进制搜索来实现。然而，绝大多数查询返回false，即只有极少数整数位于任何区间内。为了加快应用程序的速度，我正在寻找一种概率的、恒定时间的算法（某种散列函数），它可以告诉我给定的整数是否绝对不是或者可能在一个区间内。这是预期算法的草图，其中magic_data_structure使用存储在 中的间隔进行初始化tree：

x = some_integer;
if(!magic_data_structure.find(x))
  return false; // definitely not in any interval
return tree.find(x); // binary search on tree

对文学有什么想法或提示吗？非常感谢您的帮助！

PS：有人知道非重叠区间的区间树的改进（与上面描述的不同）可能包括其他区间吗？

4

1 回答 1

1

这是一个幼稚的解决方案，但始终如一。

如果您不处理大量数字，则可以只使用哈希表，其中键是数字，值是指向它们所在集合的指针。但是当然，如​​果有很多数据，它以这种方式索引它可能需要太长时间（和太多内存）。

看起来有各种不相交的数据结构和算法来存储/搜索它们，但我怀疑它们是否有恒定的时间。

于 2013-06-12T03:00:33.620 回答