Встреча посередине: 2^(n/2) вместо 2ⁿ

Коротко

Если задача распадается на две независимые половины, результаты которых склеиваются одним соотношением, перебор можно разрезать: перебрать все 2^(n/2) вариантов левой половины, все 2^(n/2) правой и соединить их поиском по словарю. Показатель вдвое меньше - и посильное n удваивается: там, где 2ⁿ кончается около двадцати, 2^(n/2) дотягивает до сорока. Замер на сумме подмножества при n = 16 и трудной цели: перебор с отсечениями 247 012 шагов, встреча посередине 4894 - в 50 раз меньше. И главное отличие: цена встречи посередине от данных почти не зависит, а цена отсечений зависит целиком.

Если ты знаешь приём «встреча посередине», его условие применимости и помнишь, что он берёт 2^(n/2) памяти, - листай до «Теперь сам».

Как думаешь, что делать, когда отсечения не работают

Вернёмся к сумме подмножества. В прошлом уроке двадцать чисел и цель 97 перебирались с отсечениями за 62 684 шага, а с сортировкой по убыванию - за 25 996. Теперь поменяем одно: цель станет 287 - это половина суммы всех двадцати чисел (сумма 575, половина округлена вниз).

Прежде чем читать дальше, подумай, что изменится. Отсечение по превышению сработает позже - сумма дольше не превысит цель. Отсечение по остатку тоже: хвоста долго хватает. Насколько подорожает перебор - вдвое? Втрое? И что делать, если подорожал он так, что не укладывается вовсе?

На что это похоже

Представь, что в толпе из сорока человек надо найти группу, которая вместе весит ровно тонну. Группа любого размера, и всех возможных групп 2⁴⁰ - больше триллиона. А можно иначе: разделить толпу на две половины по двадцать, записать веса всех возможных групп из первой половины в блокнот (их 2²⁰, около миллиона), а потом для каждой группы из второй половины просто посмотреть в блокнот: «есть ли там группа весом тонна минус моя?»

Блокнот и есть вся суть приёма. Он стоит памяти, зато превращает «перебрать все комбинации двух половин вместе» в «перебрать комбинации каждой половины отдельно и на каждую комбинацию второй один раз заглянуть в блокнот»: два миллиона действий вместо триллиона.

Механизм: разрезать, перебрать, склеить

ШАГ 1. разрезать вход на две половины по n/2 элементов

ШАГ 2. перебрать ВСЕ подмножества левой половины и запомнить их суммы
       2^(n/2) значений - это блокнот

ШАГ 3. перебрать все подмножества правой половины; для каждой суммы s
       спросить блокнот: сколько там сумм, равных (цель − s)?

ШАГ 4. сложить ответы

цена: 2 · 2^(n/2) вариантов плюс поиск по словарю
память: 2^(n/2) значений - именно за память и платим

Почему 2^(n/2) настолько меньше 2ⁿ: показатель уменьшился вдвое, а значит число вариантов стало КОРНЕМ из прежнего. 2²⁰ - это миллион, 2¹⁰ - тысяча. То есть вместо миллиона вариантов - две тысячи, по тысяче на половину.

ГРАНИЦА ПОСИЛЬНОГО (ориентир для настоящей машины, не для движка)
2ⁿ          перебор всех подмножеств        n до ~20-25
2^(n/2)     встреча посередине              n до ~40-50
                                            памяти от 2^20 до 2^25 записей

Приём работает не всегда. Условие ровно одно: вклад двух половин в ответ должен склеиваться одним соотношением, вычисляемым по частичным результатам. Для суммы это «сумма левого плюс сумма правого равна цели». Если половины взаимодействуют сложнее - например, порядок элементов из разных половин важен, - разрезать нельзя.

Правило

Встреча посередине применима, когда вход делится на две независимые половины и ответ восстанавливается из пары частичных результатов по одному соотношению. Тогда вместо 2ⁿ вариантов перебираются 2 · 2^(n/2), а пары соединяются словарём (за O(1) на запрос) или сортировкой обеих половин и двумя указателями (за O(2^(n/2) · n)). Плата - память 2^(n/2), и именно она ограничивает приём: n = 40 это миллион значений в памяти, n = 50 - 33 миллиона, n = 60 - миллиард, то есть уже нет. Суммы половины считаются НАРАЩИВАНИЕМ (к списку сумм добавляется он же с прибавленным элементом) за O(2^(n/2)), а не перебором масок с внутренним циклом по разрядам - иначе появится лишний множитель n/2. И главное свойство приёма: его цена от данных почти НЕ зависит, в отличие от цены отсечений.

Разбор: суммы половины наращиванием

Сначала - как собрать блокнот. Наивный способ - перебрать маски и для каждой сложить элементы; это 2^(n/2) масок по n/2 разрядов. Способ лучше: заметить, что суммы подмножеств первых k + 1 элементов - это суммы подмножеств первых k плюс те же суммы с прибавленным a[k].

def summy(ot, do):
    spisok = [0]
    i = ot
    while i < do:
        novye = []
        for s in spisok:
            novye.append(s + a[i])      # каждая старая сумма даёт новую
        for s in novye:
            spisok.append(s)
        i = i + 1
    return spisok

polovina = len(a) // 2
levo = summy(0, polovina)               # правая граница do не включается
pravo = summy(polovina, len(a))

Список удваивается на каждом элементе: 1, 2, 4, 8... Суммарная работа - 1 + 2 + 4 + ... + 2^(n/2), то есть примерно 2^(n/2+1) операций, без всякого множителя n. Разница заметна на замере: версия с перебором масок при n = 20 и цели 97 стоила 94 170 шагов, версия с наращиванием - 18 444, то есть в пять раз меньше.

Дальше блокнот: сколько раз каждая сумма встречается в правой половине. В схеме выше блокнот собирали из левой половины, здесь - из правой; разницы нет, половины равноправны, важно только спрашивать блокнот суммами ДРУГОЙ половины.

schet = {}
for s in pravo:
    if s in schet:
        schet[s] = schet[s] + 1
    else:
        schet[s] = 1

vsego = 0
for s in levo:
    nado = cel - s
    if nado in schet:
        vsego = vsego + schet[nado]
print(vsego)

Словарь нужен именно со счётчиком, а не множеством: подмножеств с одинаковой суммой бывает много, и каждое даёт свой ответ. Множество дало бы «есть ли хоть одно» - это другой вопрос, и для задачи «есть ли подмножество с суммой S» множества достаточно.

Разбор: где приём выигрывает, а где проигрывает

Замер на одних и тех же данных при двух разных целях. Данные - двадцать чисел прошлого урока и ещё восемь в хвост: 47, 18, 43, 31, 29, 53, 11, 37; строка с n берёт первые n чисел. Цель «половина суммы всех» - трудная: отсечения на ней почти не срабатывают. Цель 97 - лёгкая: сумма быстро превышает её. Отсечения - оба из прошлого урока; во втором столбце числа стоят как есть, в третьем отсортированы по убыванию. Всё в шагах движка.

n   цель          отсечения     отсечения + убывание   встреча посередине
12  188 (пол.)      16 246            5 159                 1 178
16  249 (пол.)     247 012           62 409                 4 894
20  287 (пол.)   не уложился      не уложился              20 170
24  357 (пол.)   не уложился      не уложился              81 550
26  398 (пол.)   не уложился      не уложился             163 533
28  422 (пол.)   не уложился      не уложился           не уложился
20  97  (лёгкая)    62 684           25 996                18 444
24  97  (лёгкая)   230 318           54 701                73 788

Два вывода, и второй важнее первого.

Первый: на трудной цели разрыв огромный и быстро растёт - при n = 16 это 50 раз против отсечений как есть и 13 раз против отсечений с сортировкой, а при n = 20 перебор не доходит уже ни в каком виде.

Второй: посмотри на столбец встречи посередине. Её цена почти одинакова для лёгкой и трудной цели - 18 444 против 20 170 при n = 20. Разница в 9% - это попадания в блокнот: на трудной цели подходящих пар 5558, на лёгкой 179. В остальном она от данных не зависит, потому что перебирает все 2^(n/2) вариантов независимо ни от чего. Отсечения, наоборот, зависят от данных целиком: на трудной цели они бессильны, а на лёгкой при n = 24 отсечения с сортировкой (54 701 шаг) даже обгоняют встречу посередине (73 788). Это разные инструменты по своей природе: отсечения дают выигрыш, когда повезёт, встреча посередине даёт гарантию. Поэтому в задаче с неизвестными заранее данными надёжнее второе.

И честная оговорка про границу: на движке курса встреча посередине кончается на n = 28, потому что предел 300 000 шагов. На настоящей машине граница - сорок-пятьдесят элементов, и первой там кончается память, а не время.

Что ломается без этого

Первое: собирать суммы перебором масок. Лишний множитель n/2 съедает часть выигрыша: 94 170 шагов против 18 444 на одной задаче. Наращивание - не микрооптимизация, это другой порядок константы.

Второе: множество вместо словаря со счётчиком. Для вопроса «существует ли» множество верно; для вопроса «сколько» оно даст заниженный ответ, потому что склеит разные подмножества с равной суммой. В нашем замере при n = 20 и цели 287 правильный ответ 5558, а со множеством вышло бы 942 - в шесть раз меньше.

Третье: разрезать задачу, в которой половины не независимы. «Выбрать подмножество так, чтобы элементы шли по возрастанию через все данные», «маршрут минимальной длины» - здесь склейка не описывается одним соотношением, и приём не применим. Признак применимости: частичный результат половины можно записать ОДНИМ числом (или коротким кортежом), и склейка - это равенство или сравнение этих чисел.

Четвёртое: забыть про память. 2^(n/2) значений при n = 40 - это миллион записей, пустяк. При n = 50 - уже 33 миллиона записей в словаре, в Python это несколько гигабайт. При n = 60 - миллиард, и такой словарь не поместится в обычную машину вовсе. Посчитать 33 миллиона сумм - дело секунд, а вот держать их негде: память кончается раньше времени, и поэтому приём не тянется дальше сорока-пятидесяти.

Пятое: делить не пополам. Если разрезать n = 24 как 8 и 16, работа станет 2⁸ + 2¹⁶ вместо 2¹² + 2¹², то есть 65 792 вместо 8192 - в восемь раз хуже. Пополам - не случайный выбор, а минимум суммы двух степеней при фиксированной сумме показателей.

Зачем это в работе

Первый сюжет - подбор пары. «Найти два платежа, которые вместе дают спорную сумму», «найти два набора настроек, которые вместе объясняют замер» - это буквально встреча посередине с блокнотом из хеш-таблицы. Приём настолько част, что его половинный случай знают все: «найти в массиве два числа с данной суммой за один проход по словарю».

Второй - криптография и подбор ключей. Классическая атака «встреча посередине» на двойное шифрование устроена так же: перебрать все варианты первой половины ключа, сложить в таблицу, перебрать вторую и искать совпадения. Из-за неё двойное шифрование даёт не удвоение стойкости, а примерно плюс один бит, и поэтому в стандарте стоит тройное.

Третий - разговор о границах. Когда коллега говорит «сорок элементов, перебор не вариант», полезно уточнить: перебор 2⁴⁰ действительно не вариант, а разрезанный пополам - вполне, если памяти хватит на миллион записей. Разница между «невозможно» и «нужно сто мегабайт памяти» - это и есть квалификация.

Теперь сам

Задача: в списке n чисел найти подмножество с суммой, как можно более близкой к C, но не больше. Как применить встречу посередине, если точного равенства не требуется?

Ответ. Блокнот надо не хешировать, а СОРТИРОВАТЬ - тогда для каждой суммы s правой половины можно искать наибольшую сумму левой, не превышающую C − s:

ШАГ 1. собрать суммы левой половины, отсортировать: 2^(n/2)·log(2^(n/2)) операций
ШАГ 2. для каждой суммы s правой половины двоичным поиском найти
       наибольшее значение ≤ C − s
ШАГ 3. запомнить лучшую найденную пару

Словарь тут не годится: он отвечает на вопрос «есть ли ровно столько», а нужен ответ «а что есть ближайшее снизу». Это общее правило: для равенства - хеш-таблица, для «ближайшего» - сортировка и двоичный поиск или два указателя по двум отсортированным спискам.

Цена вырастет на логарифм - то есть на n/2 сравнений вместо одного запроса, - и останется O(2^(n/2) · n), что для n = 40 вполне посильно. Можно отсортировать и правую половину и идти двумя указателями навстречу: двоичный поиск исчезнет, но вторая сортировка стоит тот же логарифм, так что порядок цены останется прежним, выигрыш только в константе - и следить за указателями придётся руками.

Главное

Встреча посередине - единственный приём этого раздела, который меняет ПОКАЗАТЕЛЬ с гарантией: 2ⁿ превращается в 2^(n/2), то есть в корень, на любых данных, и посильное n удваивается с двадцати до сорока. Отсечения тоже умеют сокращать дерево в сотни раз, но только когда данные позволяют, а в худшем случае оставляют все 2ⁿ. Условие применимости одно: вход делится на две независимые половины, а частичный результат каждой записывается одним числом, по которому половины склеиваются. Суммы половины считают наращиванием (O(2^(n/2))), а не перебором масок с внутренним циклом - это разница в пять раз на замере. Для «ровно столько» берут словарь со счётчиком (множество занижает ответ), для «как можно ближе» - сортировку с двоичным поиском. Платим памятью 2^(n/2), и кончается она раньше времени: n = 50 - это уже 33 миллиона записей, n = 60 - миллиард. И главный вывод в сравнении с прошлым уроком: цена отсечений зависит от данных целиком, цена встречи посередине - почти не зависит, поэтому на неизвестных данных она надёжнее.