用于在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,因为总和将会更小.