В прошлой статье я писал про эвристические методы оптимизации перебора. В этой статье я расскажу вам о ещё одной, но уже асимптотической оптимизации — meet-in-the-middle.
Типичные для этого метода снижения асимптотики: 
и 
.
Вступление
Метод заключается в том, чтобы разделить задачу пополам, получить какие-то данные и сопоставить их друг с другом.
Meet-in-the-middle имеет смысл применять, если для конкретной задачи выполняются два условия:
1) Время обработки половины данных асимптотически меньше времени получения итогового ответа.
2) Известен асимптотически более быстрый способ получения ответа для всей задачи с использованием информации об обработки её половинок.
Читать полностью »
