algorithm - 恒定时间搜索

Question

假设我有一根杆子，我把它切成了碎片。给定原始杆上的一个点，有没有办法在常数时间内找出它属于哪一 block ？

例如:

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

给定一个位置:

                                   ^
                                   |
                                   8.005

我想要第3件。

使用二进制搜索可以在 O(log n) 时间内轻松获得这样的答案，但是否可以在 O(1) 内完成？如果我以某种方式预处理“剪切”位置？

Answer 1

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

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

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