恒定时间搜索

Question

假设我有一个我切成碎片的杆.考虑到原始杆上的一点,有没有办法在恒定的时间内找出它属于哪一件？

例如:

  |------------------|---------|---------------|
  0.0                4.5       7.8532          9.123

给定一个位置:

                                   ^
                                   |
                                   8.005

我想得到3rd piece.

使用二进制搜索可以在O(log n)时间内轻松获得这样的答案,但是可以在O(1)中进行吗？如果我以某种方式预先处理"削减"位置？

Answer 1

如果您假设要查询的点是沿着杆均匀随机选择的，那么您可以得到预期的恒定时间解决方案，而不会出现疯狂的内存爆炸，如下所示。如果将杆分成 N 个等距的部分，其中 N 是杆中原始不规则间隔部分的数量，然后为 N 个相等大小的部分中的每一个记录它是原始不规则部分中的哪一个重叠，然后要进行查询，您首先只需获取查询点并进行简单的舍入以找出它位于哪个等距部分，然后使用该索引查找哪些原始线段与等距部分相交，然后然后检查每个相交的原始线段，看看该线段是否包含您的点（如果您想确保最坏情况的性能仍然是对数的，您可以使用二分搜索）。如果您假设查询点是沿着您的杆随机选择的，则此方法的预期运行时间是恒定的，并且如果您的杆最初被切成 N 个不规则的块，则内存量为 O(N)，因此没有疯狂的内存需求。

预期 O(1) 运行时间的证明：

当你计算你原来的N个不规则线段和我建议构建的N个等距线段之间的交集对的总数时，总数不超过2 *（N + 1）（因为如果你对所有端点进行排序在所有规则和不规则线段中，新的交集对总是可以被记入定义规则或不规则线段的端点之一）。因此，您有最多 2(N+1) 个不规则线段的多组，它们以某种方式分布在它们相交的 N 个规则线段中。常规线段之间交点的实际分布并不重要。当您有一个统一的查询点并计算与包含查询点的规则线段相交的不规则线段的预期数量时，每个规则线段被查询点选择的概率为 1/N，因此相交的不规则线段的预期数量需要检查的是 2*(N+1)/N = O(1)。