python - 在 Python 中执行 N*M 迭代的最快算法

Question

我不是算法专家，所以请原谅这个问题的幼稚。

我有一个包含 100K 个元素的列表 A。我有另一个包含 100K 元素的列表 B。假设 a 是列表 A 中的元素，b 是列表 B 中的元素。我想找出总和小于 100 的那些 (a, b) 组合。

一个明显的方法如下:

results = []
for a in A:
    for b in B:
        if (a+b) < 100:
            results.append((a,b))     

但是这种方法的时间复杂度是 O(n*m) = 100K * 100K，这是相当大的。是否有任何快速算法可以更有效地计算所需的输出 - 在内存和时间方面。如果是，是否可以用python实现？

Answer 1

对两个列表( O(n log n) 和 O(m log m) 进行排序，如果值受到限制，可能更少)。

然后，您可以简单地找到，对于每个 a在 A , 最大的b在 B这样 (a+b) < 100 .每个更小 b也将满足该条件。

寻找最大的 b对于一些 a可以使用二进制搜索在 B 中找到下界来完成.从最大的 a 开始向下，您可以保留 b 的列表s对应前面的a ，因为总和会变小。