如何搜索特定属性的号码列表

Question

我有一长串数字。列表中没有重复项，所有数字都可以用 2N 位表示。

对于每一对数字，我可以计算特定条件是否为真（两个数字按位异或的结果是否正好有 N 位集）。如果条件为真，我说这两个数字是相关的。我将某个数字在列表中拥有的链接数量称为排名。我需要找到列表中排名最高的数字之一。

我可以通过逐一计算每个数字的排名来在 O(n²) 内完成此操作。

是否可以做得更快？

Answer 1

对于任何给定的数字，有多少位序列满足

xor

条件？

根据中心极限定理，是

O(4^N/sqrt(N))

。更重要的是，如果我给你前

2N-10*sqrt(N)

位，那么你无法得出任何关于它是否满足你的

xor

条件的有用结论的可能性很低。

如果

4^N < n

，我们只需使用数字数据结构来计数即可获得加速。我们不是查看每个数字来查找它是否具有满足

xor

条件的特定位序列，而是计算满足条件的数字出现的次数。但如果

n

比这个小太多，大多数数字就没有足够多的其他数字足够接近它们，从而无法从对它们作为一个整体进行分析中受益。