Конспект раздела: разделяй и властвуй

Понятия

Разделяй и властвуй - три шага: разделить вход на части, решить части тем же алгоритмом, объединить ответы. Цена записывается рекуррентностью T(n) = a·T(n/b) + f(n).

Три режима этой формулы: лист тяжелее (ответ определяют рекурсивные вызовы), уровни равны (добавляется множитель log n), корень тяжелее (всё решает объединение).

Полоса - зона вокруг разреза, где могут лежать пары, разрезанные границей.

Корень из единицы - число ω с ω^n = 1; их набор самоподобен: квадраты n корней дают n/2 корней меньшего порядка.

Свёртка - c[k] = Σ a[i]·b[k−i]; умножение многочленов - её частный случай.

Что унести

Весь раздел отвечает на один вопрос: сколько стоит объединение по сравнению с числом и размером частей: f(n) сравнивают с n^(log_b a), и это сравнение решает, даст ли деление выигрыш.

T(n) = a·T(n/b) + f(n),    сравниваем f(n) с n^(log_b a)

f(n) МЕНЬШЕ   →  Θ(n^(log_b a))       работу делают листья
f(n) РАВНО    →  Θ(n^(log_b a)·log n) все уровни весят одинаково
f(n) БОЛЬШЕ*  →  Θ(f(n))              работу делает верхний вызов
* полиномиально и регулярно: 2T(n/2) + n·log n - уже Θ(n·log² n)

Видно главное: рост берётся не из числа частей и не из их размера по отдельности, а из ОТНОШЕНИЯ log_b a к стоимости объединения. Убрать одно умножение из восьми у Штрассена - значит сдвинуть показатель с 3 до 2.807; убрать одно из четырёх у Карацубы - с 2 до 1.585.

Три способа сэкономить на объединении:

1. экономия умножений  - одно произведение вместо двух за счёт сложений
                         (Карацуба: 3 из 4; Штрассен: 7 из 8; Тоом-Кук: 5 из 9)
2. геометрическое отсечение - объединять не всё, а только окрестность границы
                         (ближайшая пара: полоса шириной 2d, семь соседей по y)
3. смена представления - перейти туда, где операция дешёвая
                         (БПФ: в значениях умножение поточечное)

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

Порог выгоды всегда замеряют. У всех алгоритмов раздела большая константа, и на малых входах простой алгоритм быстрее: сортировка слиянием переключается на вставки около 10-30 элементов, Штрассен окупается на сотнях, БПФ - на сотнях-тысячах. Точный порог зависит от машины, и его измеряют, а не выводят.

Тихие ошибки раздела: считать, что деление пополам ускоряет что угодно (при тяжёлом объединении выигрыша нет вовсе); забыть про случаи, задевающие границу (ответ молча завышается); брать в БПФ длину без запаса на весь результат (циклическая свёртка вместо обычной); переносить NTT с большим модулем в арифметику с 53 битами точности; ждать целых чисел от комплексного БПФ.

Куда это ведёт

Дальше - жадные алгоритмы: там задача не делится, а решается по шагам, и каждый шаг выбирается локально. Главная работа там не в коде, а в доказательстве, что локальный выбор не портит будущее. Чуть позже, в разделе про динамическое программирование, вернётся идея этого раздела - но для случая, когда части ПЕРЕСЕКАЮТСЯ, и решать их заново становится дорого.