Конспект: схема и её стоимость

Понятия

Разделяй и властвуй - три шага: разделить задачу на a подзадач размера n/b, решить их рекурсивно, объединить ответы.

цена:  T(n) = a·T(n/b) + f(n)
       a    - сколько подзадач
       b    - во сколько раз каждая меньше
       f(n) - ВСЯ работа вне рекурсии: деление плюс объединение

Порог - размер куска, ниже которого выгоднее простой алгоритм без рекурсии (в библиотеках 16-64 элемента). Снизу вверх - развёртка рекурсии в цикл по удваивающимся кускам.

Что унести

Главная теорема читает формулу одним сравнением n^(log_b a) с f(n):

2·T(n/2) + n    → Θ(n·log n)     сортировка слиянием, максимальный подотрезок
1·T(n/2) + 1    → Θ(log n)       двоичный поиск
1·T(n/2) + n    → Θ(n)           сумма n + n/2 + n/4 + ... < 2n
4·T(n/2) + n    → Θ(n²)          наивное умножение матриц
3·T(n/2) + n    → Θ(n^1.585)     Карацуба: одно умножение сэкономлено
2·T(n/2) + n²   → Θ(n²)          деление не дало ничего

Выигрыш даёт дешёвое объединение, а не деление само по себе. Убивают его три вещи: дорогое объединение, слишком много подзадач и слишком мелкое дробление. Первые две видны в асимптотике, третья - только в замере.

Схема требует НЕЗАВИСИМЫХ подзадач. Перекрываются - получится экспонента: F(n) = F(n−1) + F(n−2) честным делением считается за 1.618^n, хотя ответ линеен. Это признак динамического программирования.

Приёмы поверх схемы: развернуть рекурсию в цикл снизу вверх (нет стека и вызовов, но на размерах не кратных степени двойки нужен min по границе); завести ОДИН буфер снаружи рекурсии; считать независимые половины параллельно (потолок ускорения ставит последовательное объединение); делить на неравные части можно, но тогда цену считают деревом, а не теоремой.

Тихие ошибки: mid = (lo + hi) // 2 переполняется в языках с фиксированными целыми; рекурсия до одного элемента вместо порога; буфер внутри рекурсии; забытый базовый случай; главная теорема, применённая к частям разного размера.

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

Следующая глава - умножение: Карацуба и Штрассен. Там видно, как экономия ОДНОГО умножения меняет a в формуле и вместе с ним порядок роста - n² превращается в n^1.585.