Блог

Если задан ввод [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 
  

Но мне интересно, есть ли какие-то методы, которые могут ускорить этот процесс. Спасибо!

Нет, их нет. Поскольку вы оставили и последовательности, и свойства как абстрактные сущности, мы не можем использовать внутреннюю информацию, чтобы избежать основного требования: мы должны проверять каждый элемент в списке. Это делает O (N) теоретическим минимумом.