Разделяй и властвуй

Три задачи. Отсортировать 19 073 землетрясения по глубине. Найти среди них медианную глубину. Перемножить две половины числа 300! — произведения 1·2·…·150 и 151·…·300. Все три решаются одним приёмом: разрезать задачу на части, решить части тем же способом и склеить ответ. А стоят они по-разному. Ниже — дерево рекурсии каждой из них в разрезе: полоса — сколько работы сделано на уровне, перегородки в полосе — подзадачи этого уровня. Переключайте задачи и двигайте размер.

Картины три, и они не похожи. У сортировки уровни почти одинаковые: каждый стоит около 19 тысяч сравнений, потому что на каждом уровне сливается весь каталог, только кусками разной длины. Уровней пятнадцать, и всего выходит 245 169 сравнений — примерно n log₂ n. У медианы полосы тают сверху вниз: быстрый выбор продолжает только в одной части, и работа сосредоточена наверху; весь поиск стоит 57 124 сравнения, втрое больше числа землетрясений. У умножения наоборот: каждый уровень в полтора раза дороже предыдущего, и основная работа — внизу, в листьях, где перемножаются отдельные цифры.

Попробуйте сломать картину. У медианы включите отсортированный ряд с первым опорным — и дерево вытянется в столб из сотен уровней. У умножения включите четыре произведения вместо трёх — и каждый уровень станет вдвое дороже предыдущего. Обе поломки объясняет одна теорема, к ней и идём.

Идея

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

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

Чтобы приём сработал, нужны три вещи. Подзадачи должны быть того же вида, что исходная, — иначе рекурсии не на что опереться. Они должны быть заметно меньше — в разы, а не на единицу. И склеивать ответы должно быть дешевле, чем решать задачу заново. Где это нарушено, приём перестаёт помогать; таким случаям ниже отведён отдельный раздел.

Дерево рекурсии

Нарисуем все вызовы как дерево. В корне — задача размера n, у каждого узла a детей, размер падает в b раз с каждым уровнем. Это дерево рекурсии, и время алгоритма — сумма работы всех его узлов. Складывать удобнее по уровням. На уровне i стоят aⁱ подзадач размера n/bⁱ, и если склейка задачи размера m стоит m^d, уровень в целом стоит

$$a^i \cdot \left(\frac{n}{b^i}\right)^{d} = n^d \cdot \left(\frac{a}{b^d}\right)^{i}.$$

Работа уровней — геометрическая прогрессия со знаменателем q = a/b^d, и всё решает этот знаменатель: каждый уровень дороже предыдущего, дешевле или такой же. В первой сцене это видно прямо по полосам. У сортировки a = 2, b = 2, d = 1, и q = 1: полосы равны. У медианы подзадача одна, и q = 1/2: полосы тают вдвое. У Карацубы q = 3/2, у четырёх произведений q = 2: полосы растут.

Настоящие полосы не совсем ровные, и это поучительно. Нижние уровни сортировки дешевле верхних: короткие куски сливаются быстрее, чем на сравнение на каждый элемент, потому что один из кусков часто кончается раньше. Медиана тает неравномерно: опорный элемент на настоящих данных иногда попадает неудачно, и после первого же разбиения кусок уменьшился всего на сотню землетрясений из 19 тысяч. Уравнение описывает дерево в целом, а не каждый его узел.

Основная теорема

Доказательство даёт больше, чем формулировка: оно говорит, куда смотреть, чтобы ускорить алгоритм. В первом случае всё время уходит на склейку в корне, и ускорять надо её. В третьем склейка почти ничего не стоит, а платим мы за число листьев n^{log_b a}: Карацуба уменьшил a с четырёх до трёх и этим изменил показатель степени с 2 до log₂ 3 ≈ 1,585. Во втором случае важны оба множителя. Для степеней двойки уравнения решаются точно: T(n) = T(n/2) + n даёт 2n − 1, уравнение 2T(n/2) + n даёт n log₂ n + n, а 3T(n/2) + n даёт 3n^{log₂ 3} − 2n (во всех трёх T(1) = 1).

Проверим теорему замером. Ниже те же пять программ на задачах растущего размера; оси логарифмические, поэтому степень n выглядит прямой, а её наклон — показатель степени.

Наклоны совпадают с предсказанием: около единицы у медианы, чуть больше единицы у слияния — так на логарифмических осях выглядит n log n, около 1,6 у Карацубы и около двух у четырёх произведений и у сломанной медианы.

Где теорема молчит

Теорема покрывает не все уравнения, и полезно знать границы.

Склейка не степенная. Если f(n) = n log n при a = b = 2, то ни один случай не подходит: f растёт быстрее n, но медленнее любой n^1+ε. Посчитаем по уровням: уровень i стоит n log(n/2ⁱ), и сумма по log n уровням даёт Θ(n log² n). Так выходит у ближайшей пары точек, если в каждом вызове заново сортировать полосу; отсортировав точки заранее, склейку делают линейной и возвращаются к n log n. Более общая форма теоремы разрешает любые f(n), отделённые от n^{log_b a} степенью, а в третьем случае требует ещё, чтобы склейка на уровне ниже была заметно дешевле: a·f(n/b) ≤ c·f(n) для какого-то c < 1.

Части разного размера. Медиана медиан — быстрый выбор с гарантией — решает задачу на пятой части и задачу на семи десятых: T(n) ≤ T(n/5) + T(7n/10) + n. Теорема с одним b тут не годится, но дерево рекурсии отвечает сразу: суммарный размер подзадач на каждом уровне не больше 1/5 + 7/10 = 9/10 от предыдущего, работа уровней — убывающая прогрессия, и всё вместе — Θ(n). Общий ответ для таких уравнений дали Мохамад Акра и Луай Баззи в 1998 году.

Части не в разы меньше. Сломанная медиана из первой сцены отрезает по одному элементу: T(n) = T(n − 1) + n. Здесь нет b > 1, глубина дерева — n, а не log n, и сумма n + (n − 1) + … даёт Θ(n²). На тысяче отсортированных землетрясений листинг ниже насчитал 501 уровень и 375 750 сравнений — почти ровно 3/8 · 1000².

Код

Три задачи первой сцены в виде программ. Каждая сообщает, сколько работы сделала на каком уровне: сортировка — сравнения при слиянии, быстрый выбор — сравнения с опорным, умножение — длину чисел, которые проходят через сложения и сдвиги в каждом узле, а в листьях — умножения цифр. Числа складываются цифрами в списках, без встроенной длинной арифметики, чтобы её работу было видно.

Karatsuba, three products: 263 and 352 digits of 300! (digits handled)
  level  subproblems       work  next/this
      0            1        352      1.50
      1            3        528      1.50
      2            9        794      1.51
      3           27       1197      1.51

Карацуба перемножил числа из 263 и 352 цифр за 21 897 умножений цифр. Столбик потратил бы 263 · 352 = 92 576, а деление пополам без хитрости — 203 776: само по себе разрезание ничего не даёт, и из-за выравнивания длин половин выходит даже больше, чем у столбика. Выигрыш приносит только третье произведение вместо четвёртого.

Сколько стоит сам приём

Время даёт основная теорема, но у алгоритмов этого рода есть ещё три статьи расходов, о которых она молчит.

Память на рекурсию. Стек держит одну ветку дерева, то есть log_b n кадров, если части уменьшаются в разы. Для миллиона элементов и b = 2 это двадцать кадров. А вот если части уменьшаются на единицу, как у сломанной медианы или у быстрой сортировки на неудачном входе, глубина становится n, и Python остановит рекурсию около тысячи уровней. Отсюда правило из быстрой сортировки: рекурсивно уходить в меньшую часть, а большую обрабатывать в цикле — тогда глубина не больше log₂ n. Сверх стека бывает память на склейку: сортировка слиянием держит буфер на n элементов.

Мелкие подзадачи. Внизу дерева узлов больше всего, и накладные расходы — вызов функции, нарезка, выделение памяти — там стоят дороже полезной работы. Поэтому настоящие реализации доводят рекурсию не до одного элемента, а до порога и дальше решают простым способом: слияние переходит на вставки на кусках из нескольких десятков элементов (замер есть в статье о сортировке слиянием), Карацуба в библиотеках длинной арифметики переходит на столбик на числах из нескольких десятков машинных слов (подробности — в статье об умножении Карацубы). Порог не меняет асимптотику, но меняет постоянный множитель в разы.

Параллельность. Подзадачи независимы, и их можно отдать разным ядрам. Если ядер сколько угодно, время определяется не суммой работы, а самой длинной цепочкой зависимостей — по одному узлу на каждом уровне. У сортировки слиянием это склейка в корне за Θ(n), поэтому параллельное слияние само делят на части; у умножения Карацубы три подзадачи независимы, и на каждом уровне их можно считать одновременно.

Когда приём не помогает

Подзадачи повторяются. Рекурсия F(n) = F(n − 1) + F(n − 2) похожа на разделяй и властвуй, но её подзадачи пересекаются: F(n − 2) считается и из корня, и из F(n − 1), и дерево вызовов растёт экспоненциально. Когда одни и те же подзадачи встречаются снова и снова, их надо запоминать — это мемоизация и динамическое программирование. Разделяй и властвуй хорош, когда части не пересекаются.

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

Частей слишком много. Четыре произведения половин дают q = 2, и дерево рекурсии стоит столько же, сколько столбик: разрезание переложило работу в листья и ничего не сэкономило. Приём выигрывает, только если a удаётся сделать меньше, чем очевидные b² или b³: так поступили Карацуба для чисел и Штрассен для матриц.

Части неравны. Если разрез отделяет кусок постоянного размера, глубина становится линейной, и n log n превращается в n²: это худший случай быстрой сортировки и сломанная медиана из сцены. Лечат случайным выбором опорного элемента или медианой медиан.

История

Приёмом пользовались задолго до того, как его назвали. Джон фон Нейман в 1945 году описал сортировку слиянием, Анатолий Карацуба в 1960-м нашёл умножение с тремя произведениями половин (история опровергнутой гипотезы Колмогорова рассказана в главе курса), Джеймс Кули и Джон Тьюки в 1965-м опубликовали быстрое преобразование Фурье, Фолькер Штрассен в 1969-м — умножение матриц с семью произведениями вместо восьми. Каждый раз время работы выводили отдельно.

Общий способ решать такие уравнения описали в 1980 году Джон Бентли, Доротея Хакен и Джеймс Сакс в заметке «A general method for solving divide-and-conquer recurrences»: дерево рекурсии и сумма работы по уровням, как в этой статье. Под названием «основная теорема» (master theorem) результат вошёл в первое издание учебника Кормена, Лейзерсона и Ривеста в 1990 году, и с тех пор его учат почти в каждом курсе алгоритмов. Уравнения с частями разного размера Акра и Баззи решили в 1998 году.

Задачи

В первой задаче нужно построить квадродерево настоящей фотографии для многих порогов сразу; решение в лоб пересчитывает каждый квадрат заново, а хорошее склеивает ответ из четырёх четвертей за постоянное время — ровно та разница между вторым и третьим случаем теоремы. Во второй задаче разделяй и властвуй строит ответ сам: нужно уложить плитку-уголок на пол с колонной.