Изменения

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

Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые <tex> 4 </tex> числа, сумма которых равна <tex> 0 </tex> (одинаковые элементы могут быть использованы несколько раз).

Если вместо отсортированного массива использовать [[Хеш-таблица | хэш-таблицу]], то задачу можно будет решить за время <tex> O(N^2) </tex>.

== Задача о рюкзаке ==