时间复杂度优于O（n**2）的成对比较算法-解网

问：

我有大约 500,000 个 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'， 'R'， 'R'， 'R'， 'R'， 'F'， 'G'， 'H'， 'I'， 'J']

如果我们将 1 用于两个数组包含相同单词的位置，将 0 用于它们包含不同单词的位置，则 a 与 b 的交集将表示为 [1， 0， 1， 0， 1， 0， 1， 0， 1， 0];a 与 z 的交集将表示为 [0， 0， 0， 0， 0， 1， 1， 1， 1， 1] 等。

我们能比朴素的 O（n**2）算法做得更好吗，即一个 for 循环在另一个 for 循环中？

成对 Python 性能比较

[[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},
...}

这可以解释为检查两个条目是否对应Entry 6, 18, 24 and 26 have the same value in position 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]

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

Pairwise comparison algorithm with time complexity better than O(n**2)

评论

评论