Изменения

'''Meet-in-the-middle''' (Встреча в середине) — это метод решения уравнения вида <tex> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> {O((X \log{X} + Y)\logtimes{h({X})}})</tex>, где <tex> {h({X})} </tex> время поиска <tex> {g({y})} </tex> в множестве <tex> {X} </tex>.}}'''Meet-in-the-middle''' разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом : переберем все возможные значения <tex> {x} </tex> и запишем пару значений <tex> ({x},{f({x})}) </tex> в массив, который мы отсортируем по второму элементу (значению функции). Затем будем перебирать всевозможные значения <tex> {y} </tex>, для каждого из них будем вычислять <tex> f({y}) </tex>, которое мы будем искать в нашем отсортированном массиве. Таким образом, время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\logtimes{h({YX}))}} </tex> на двоичный поиск, что дает в сумме <tex>{O((X \log{X} + Y)\logtimes{h({X})}})</tex>.