Meet-in-the-middle
Meet-in-the-middle - способ оптимизации решений, заключающийся в том, чтобы разбить исходную задачу на две половины, решить каждую независимо и затем получить решение исходной задачи путем объединения решений половин.
Соответственно, имеет смысл применять
meet-in-the-middle, если выполняются два условия.
1) Время, необходимое для решения половины задачи, асимптотически меньше времени решения целой задачи.
2) По решению задач-половин можно получить решений исходной целой задачи и при этом асимптотически быстрее, чем просто решить целую задачу.
Пример
Пусть имеется четыре массива целых чисел
A,
B,
C и
D. Необходимо выбрать из каждого массива ровно одно число, чтобы сумма этих чисел была равна нулю. Можно использовать наивное решение, а именно, просто перебрать все возможные варианты. Это будет работать за
О(n4).
Однако, мы можем воспользоваться
meet-in-the-middle.
Заметим, что
a + b + c + d = 0 эквивалентно тому, что
(a + b) = -(c + d).
Разделим задачу на две половины, а именно, в первой половине будем использовать только массивы
A и
B, а во второй половине только
C и
D.
Переберем все возможные варианты
(a + b) в первой половине и сохраним все значения в хэш-таблицу (
unordered_map,
HashMap или т.п.). Это работает за
O(n2).
Теперь будем перебирать все возможные варианты
(c + d) во второй половине. При рассмотрении определенного варианта будем проверять, есть ли в хэш-таблице значение, ассоциированное с противоположной по знаку текущей суммой (тогда нашли два обратных числа, которые в сумме дают ноль). Эта часть также работает за
O(n2).
Здесь у нас нет отдельной фазы "
объединения ответов" в один, мы делали это по ходу решения для каждой из половин. В большинстве задач будет аналогичная ситуация.
В итоге мы получили решение за
O(n2), используя
meet-in-the-middle.
Стоит обратить внимание, что чаще всего
meet-in-the-middle применяется при оптимизации экспоненциальных решений, что значительно влияет на время работы.