找到满足特定属性的元素对

Question

如果给定输入 [s1, ..., sn]，并且还给定属性 P，则程序应输出满足该 P 的连续对。

例如，如果 P 是该对中两个元素的总和应小于 20，则输入[1,10,29,17]应输出，[(1,10)]因为它是满足此 P 的唯一连续对。

为了简单起见，我们假设检查属性 P 是常数时间。一个简单的解决方案是循环遍历列表，使其复杂度为 O(n)。

例如在Python中

def f(ls, P: callable):

    r = []

    for i in range(len(ls)-1):

        if P(ls[i], ls[i+1]):

            r.append((ls[i], ls[i+1]))

    return r

assert f([1,10,29,17], lambda x, y: x+y<=20) == [(1,10)]

assert f([1,10,29,17], lambda x, y: x < y) == [(1,10),(10,29)] # checking if first is smaller than the second 

但我想知道是否有一些方法可以加快这个过程。谢谢你！

Answer 1

不是，没有。由于您已将序列和属性保留为抽象实体，因此我们没有可以利用的固有信息来避免基本要求：我们必须检查列表中的每个元素。这使得O(N)成为理论最小值。