MITM: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Содержимое страницы заменено на «* MITM в задачах на числа»)
Метка: замена
Строка 1: Строка 1:
 +
==Идея==
 +
Пусть мы умеем полным перебором находить ответ, допустим за $O(2^n * poly(n))$, где $poly(n)$ - полином от $n$, давайте теперь научимся решать эту задачу за $O(2^(n / 2) * poly(n))$
 +
 +
==Решение==
 +
 +
Давайте разделим задачу на две части - и сначала решим честно перебором за $O(2^{n / 2} * poly(n))$, теперь сделаем следующее : запомним ответы для всех вариантов в какое-то удобное для нас хранилище(в общем случае нам подойдет hash-map), теперь насчитаем ответы для всех вариантов в левой части и для каждого из них посмотрим есть ли подходящий нам пример в правой части.
 +
 +
* [[MITM в задаче о рюкзаке]]
 
* [[MITM в задачах на числа]]
 
* [[MITM в задачах на числа]]
 +
* [[MITM в задаче о числах из 1 и 2, делящихся на $M$]]

Версия 17:39, 25 марта 2020

Идея

Пусть мы умеем полным перебором находить ответ, допустим за $O(2^n * poly(n))$, где $poly(n)$ - полином от $n$, давайте теперь научимся решать эту задачу за $O(2^(n / 2) * poly(n))$

Решение

Давайте разделим задачу на две части - и сначала решим честно перебором за $O(2^{n / 2} * poly(n))$, теперь сделаем следующее : запомним ответы для всех вариантов в какое-то удобное для нас хранилище(в общем случае нам подойдет hash-map), теперь насчитаем ответы для всех вариантов в левой части и для каждого из них посмотрим есть ли подходящий нам пример в правой части.