时间复杂度优于O(n**2)的成对比较算法

Question

我有大约50万个10字数组，即500,000字10克。对于每10克，我需要知道在哪个位置，如果有的话，其余的499,999 10克有相同的元素：

A= 'A'，'B'，'C'，'D'，'E'，'F'，'G'，'H'，'I'，'J‘

B= 'A'，'M'，'C'，'M'，'E'，'M'，'G'，'M'，'I'，'M‘

..。

Z= 'R'，'F'，'G'，'H'，'I'，'J‘

如果对两个数组包含相同单词的位置使用1，对于包含不同单词的位置，则a与b的交集将表示为1、0、1、0、1、1、0、1、0；a与z的交集将表示为0、0、0、0、0、1、1、1、1、1、1等。

我们能比简单的O(n**2)算法做得更好吗？

Answer 1

有趣的问题:)

所以我有一个想法，我认为它是O(n*log(n) + n)，在这里，+n渐近无关。

因此，我提出以下建议：

tuple_len = 10
min_value = 1
max_value = 10
number_of_entries = 100
l = [[j] + [randint(min_value,max_value) for i in range(tuple_len)] for j in range(number_of_entries)]

基组：

[[0, 9, 10, 3, 6, 3, 10, 9, 7, 8, 4],
 [1, 2, 3, 6, 7, 9, 2, 5, 10, 6, 10],
 [2, 5, 4, 10, 8, 5, 9, 2, 7, 4, 3],
 [3, 5, 9, 4, 5, 5, 3, 10, 1, 4, 4],
 [4, 9, 10, 9, 10, 9, 10, 6, 1, 6, 2],
 [5, 5, 6, 3, 6, 9, 5, 8, 3, 1, 1],
 [6, 9, 7, 5, 5, 5, 2, 1, 2, 3, 6],
 [7, 2, 6, 9, 10, 5, 6, 7, 3, 7, 5],
 [8, 6, 8, 9, 3, 7, 1, 2, 9, 8, 10],
 [9, 7, 5, 7, 2, 1, 3, 7, 1, 2, 9],
 [10, 1, 4, 4, 3, 6, 9, 6, 3, 3, 8],
 [11, 8, 3, 10, 10, 5, 9, 7, 3, 4, 5],
...]

所以，为了方便起见，我使用了数字，并将列表中的位置作为第一个值添加。

我建议依次为数据的每一列排序数据集，其中排序为O(n*log(n))，然后将具有相同值的所有条目的位置值添加到集合中，即O(n)。结果如下所示：

[{6, 18, 24, 26},
 {22, 34},
 {1, 6, 19, 31, 57, 58},
 {1, 9, 18},
...}

如果两个条目对应于Ò(1)，则可以将其解释为Ò(1)检查

true if (a in match_set) and (b in match_set) else false

代码示例如下：

match_sets = [set() for i in range(tuple_len)]


for position in range(tuple_len):
    l = sorted(l, key= lambda x: x[position+1])
    last_value = l[0][position+1]
    for entry in range(number_of_entries):
        if l[entry][position + 1] == last_value:
            match_sets[position].add(l[entry][0])
            last_value = l[entry][position + 1]