Разделяй и властвуй: три шага и одна формула цены

Коротко

Схема простая: раздели задачу на несколько таких же поменьше, реши их тем же способом, объедини ответы. Вся цена укладывается в одну строчку - T(n) = a·T(n/b) + f(n), где a - сколько получилось подзадач, b - во сколько раз каждая меньше, f(n) - цена деления и объединения. Выигрыш берётся не из самого деления, а из того, что СУММА работы на уровнях растёт медленнее, чем при переборе. И он исчезает, как только объединение становится дороже: T(n) = 2·T(n/2) + n даёт n·log n, а T(n) = 2·T(n/2) + n² - те же n², что и у наивного решения.

Если ты умеешь по коду выписать a, b и f(n), знаешь, какой из трёх случаев главной теоремы получится, и понимаешь, когда деление не даёт ничего, листай до «Теперь сам».

Как думаешь, почему деление вообще помогает

Отсортировать миллион чисел перебором пар - это 10¹² сравнений. Разделишь пополам - получишь две задачи по полмиллиона, то есть 2 · (5·10⁵)² = 5·10¹¹. Уже вдвое меньше, и это ещё до всякой рекурсии.

Вот тут и спрятан ответ: квадрат от половины - это четверть квадрата, а половин две, значит одно деление срезает работу вдвое. Делить можно log n раз - пока куски не станут по одному элементу, и дробить дальше нечего. Квадратичная работа при этом исчезает совсем: на каждом уровне остаётся только склейка, n операций, а уровней log n - отсюда и n·log n. Но это верно лишь если склеить половинки можно дёшево, и вот это условие решает всё.

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

Разбор завала на складе. Одному человеку перебрать тысячу коробок - день. Позвать двоих, разделить склад пополам, каждому по пятьсот - и дальше каждый делит свою половину снова. Работа тает вдвое на каждом шаге. Но если в конце все коробки надо СВЕСТИ в один общий список вручную, сверяя каждую с каждой, - выигрыш от деления съест именно эта сверка. Дешёвое объединение - вот чем оплачивается вся схема.

Механизм: три шага и уравнение цены

разделить   - разбить задачу размера n на a подзадач размера n/b
решить      - каждую тем же алгоритмом (рекурсия), пока не упрёмся в базовый случай
объединить  - собрать ответ задачи из ответов подзадач

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

Главная теорема из раздела про рекуррентности читает эту строчку сразу:

сравниваем n^(log_b a) с f(n)

листья тяжелее      → T(n) = Θ(n^(log_b a))     вся работа внизу
поровну             → T(n) = Θ(n^(log_b a)·log n)
корень тяжелее      → T(n) = Θ(f(n))            вся работа наверху

Дерево рекурсии для T(n) = 2·T(n/2) + n. Размер задач падает вдвое, но задач становится вдвое больше - суммарная работа на КАЖДОМ уровне одна и та же, n. Уровней log₂ n, отсюда и n·log n.

Правило

Разделяй и властвуй - это три шага (разделить, решить рекурсивно, объединить) и одна формула цены T(n) = a·T(n/b) + f(n), где f(n) - вся работа вне рекурсии. Выигрыш даёт не деление само по себе, а соотношение между числом подзадач и ценой объединения: его читает главная теорема, сравнивая n^(log_b a) с f(n). Схема применима, когда подзадачи НЕЗАВИСИМЫ; если они перекрываются, каждая будет считаться много раз - это признак динамического программирования, а не деления пополам.

Разбор: одно и то же деление с разной ценой объединения

Возьмём три алгоритма, у которых деление одинаковое - пополам, две подзадачи, - и посмотрим, что решает.

сортировка слиянием   T(n) = 2·T(n/2) + n        слияние двух отсортированных половин - линейно
                      n^(log₂ 2) = n,  f(n) = n  → поровну → Θ(n·log n)

двоичный поиск        T(n) = 1·T(n/2) + 1        половина отбрасывается целиком
                      n^(log₂ 1) = 1, f(n) = 1   → поровну → Θ(log n)

выдуманный алгоритм   T(n) = 2·T(n/2) + n²       объединение квадратично
                      n^(log₂ 2) = n,  f(n) = n² → корень тяжелее → Θ(n²)

Третья строчка - и есть ответ на вопрос «зачем вообще думать про объединение». Деление там точно такое же, как у сортировки слиянием, рекурсия честная, половинки решаются быстрее - а итог тот же квадрат, что у перебора. Вся экономия ушла в склейку.

Проверим это арифметикой, без теоремы. Верхний уровень стоит n². Второй - 2·(n/2)² = n²/2. Третий - 4·(n/4)² = n²/4. Сумма n² · (1 + 1/2 + 1/4 + ...) меньше 2n². То есть на верхний уровень приходится больше половины всей работы, и сколько бы уровней ни было ниже, они ничего не меняют.

Разбор: когда делить нельзя, хотя хочется

Схема требует, чтобы подзадачи были НЕЗАВИСИМЫ. Вот пример, где это нарушается.

сколько есть способов подняться по лестнице из n ступенек шагами по 1 и 2?

делим: F(n) = F(n−1) + F(n−2)

выглядит как «разделяй и властвуй» - но подзадачи ПЕРЕСЕКАЮТСЯ:
F(n−2) считается и внутри F(n−1), и отдельно

Посчитаем цену такого «деления»: T(n) = T(n−1) + T(n−2) + 1 - это числа Фибоначчи, то есть рост примерно 1.618^n. Экспонента там, где ответ считается за линию, если запоминать уже посчитанное.

Отличать эти два случая надо ДО того, как писать код. Признак простой: посмотри, могут ли две подзадачи запросить одно и то же. У сортировки слиянием левая половина и правая не пересекаются вовсе - каждый элемент лежит ровно в одной. У лестницы F(n−1) и F(n−2) пересекаются почти целиком. Первый случай - деление пополам, второй - динамическое программирование из своего раздела.

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

Первое: делить, не посчитав цену объединения, - и получить ту же асимптотику, что у перебора, плюс рекурсию сверху. Второе: писать mid = (lo + hi) / 2 вместо lo + (hi − lo) // 2: на больших индексах первая форма переполняется в языках с фиксированными целыми (в Python обойдётся, в C и Java - нет, и это знаменитая ошибка в двоичном поиске, прожившая в стандартной библиотеке двадцать лет). Третье: забыть базовый случай или сделать его неправильным - рекурсия уйдёт в бесконечность на массиве из одного элемента. Четвёртое: применять схему к перекрывающимся подзадачам и удивляться экспоненте. Пятое: считать, что «пополам» обязательно: подзадач бывает три (a = 3), а деление - не обязательно на равные части; формула цены от этого не меняется, а вот ответ - да.

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

Половина того, что уже разобрано в курсе, - это деление пополам: сортировка слиянием, быстрая сортировка, двоичный поиск, поиск порядковой статистики, дерево отрезков. Дальше в этом разделе будут умножение Карацубы, ближайшая пара точек и быстрое преобразование Фурье. Но главное - привычка: увидев задачу «на весь массив», спроси себя, что будет, если разрезать его пополам, и СКОЛЬКО стоит склеить ответы. Если склейка линейна - почти наверняка получится n·log n вместо квадрата. Плюс приятный побочный эффект: независимые подзадачи считаются параллельно без всякой синхронизации, поэтому эта схема - первое, что переносят на несколько ядер.

Теперь сам

Для каждой рекуррентности назови a, b, f(n) и ответ: (1) T(n) = 4·T(n/2) + n, (2) T(n) = T(n/2) + n, (3) T(n) = 3·T(n/2) + n.

Ответ.

(1) a = 4, b = 2, f(n) = n. Считаем n^(log₂ 4) = n². Сравниваем с f(n) = n: листья тяжелее, значит T(n) = Θ(n²). Смысл: четыре подзадачи половинного размера - это как раз умножение длинных чисел столбиком, где каждая половина одного множителя встречается с каждой половиной другого (глава про Карацубу начинается ровно с этой формулы), и деление тут не даёт ничего.

(2) a = 1, b = 2, f(n) = n. Считаем n^(log₂ 1) = n⁰ = 1. Корень тяжелее, значит T(n) = Θ(n). Смысл: одна подзадача вдвое меньше плюс линейная работа - геометрическая сумма n + n/2 + n/4 + ... < 2n.

(3) a = 3, b = 2, f(n) = n. Считаем n^(log₂ 3) = n^1.585. Листья тяжелее, значит T(n) = Θ(n^1.585). Это ровно умножение Карацубы из следующей главы: три умножения вместо четырёх превращают n² в n^1.585.

Сравни первый и третий ответы: разница между a = 4 и a = 3 при том же делении - это разница между n² и n^1.585. Одно сэкономленное умножение меняет ПОРЯДОК РОСТА, и почему так - тема следующей главы.

Главное

Разделяй и властвуй: разделить задачу на a подзадач размера n/b, решить их рекурсивно, объединить ответы. Цена - T(n) = a·T(n/b) + f(n), где f(n) вся работа вне рекурсии; читается главной теоремой сравнением n^(log_b a) с f(n). Выигрыш даёт дешёвое ОБЪЕДИНЕНИЕ: при 2·T(n/2) + n получается n·log n, при 2·T(n/2) + n² - те же n², что у перебора. Схема требует НЕЗАВИСИМЫХ подзадач: если они перекрываются, честное деление даёт экспоненту, и задача относится к динамическому программированию. Число подзадач a влияет на ответ сильнее всего: 4·T(n/2) + n это n², а 3·T(n/2) + n - уже n^1.585.