MITM: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) |
|||
(не показано 5 промежуточных версий 1 участника) | |||
Строка 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 в задаче о числах из 1 и 2, делящихся на M]] | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | |||
+ | [[Категория:Конспект]] |
Текущая версия на 21:27, 8 мая 2020
Идея
Пусть мы умеем полным перебором находить ответ, допустим за $O(2^n * poly(n))$, где $poly(n)$ - полином от $n$, давайте теперь научимся решать эту задачу за $O(2^{n / 2} * poly(n))$
Решение
Давайте разделим задачу на две части - и сначала решим честно перебором за $O(2^{n / 2} * poly(n))$, теперь сделаем следующее : запомним ответы для всех вариантов в какое-то удобное для нас хранилище(в общем случае нам подойдет hash-map), теперь насчитаем ответы для всех вариантов в левой части и для каждого из них посмотрим есть ли подходящий нам пример в правой части.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin