Ссылка на первую часть.

Мастер-теорема

На примере из прошлой части, попробуем сформулировать и обобщить принцип «Разделяй и властвуй». Мы беремся за проблему, размера n, делим эту проблему на подзадачи размером n/b. Количество таких подзадач обозначим числом a. И еще имеется задача скомпоновать результаты выполнения этих a задач размером n/b в итоговый результат для задачи размера n, который будем считать задачей полиномиальной сложности степени c, O(n^c) . Если задача компоновки будет не полиномиальной, то все изложение резко усложнится. Поэтому, давайте позволим задаче компоновки быть полиномиальной, тем более в это попадает очень большое количество алгоритмов.

В примере выше, произведения двух чисел, мы разделили задачу длины n на три подзадачи длины n/2 и компоновали результат линейными операциями O(n). Значит, для этого случая: a=3, b=2, c=1.

Выше мы уже выводили рекуррентную формулу для рекурсивного алгоритма метода "Разделяй и властвуй", которую просто обобщим:

Мастер-теорема. Пусть имеются рекуррентные соотношения:

Тогда асимптотическое решение имеет вид:

Собственно, в прошлой части мы уже решали эту задачу, просто напомню. Строим рекурсивное дерево, где из узла-задачи длины n на уровни ниже расходятся a задач длины n/b. Высота дерева log_b(n). Давайте для упрощения считать, что n это целая степень b, тогда и не надо мучиться с округлением и высота дерева целой будет. Это все таки не математическая публикация, а научно-популярная, поэтому давайте сделаем это упрощение.

На самом нижнем уровне рекурсивного дерева у нас n^log(a)задач размером O(1).

На уровнях выше выполняются задачи по компоновке результатов предыдущего уровня. Всего на уровне k будет a^k таких задач, каждая со сложностью O((n/b^k)^c).

Таким образом, для оценки всего алгоритма нам нужно посчитать сумму сложности по всем уровням рекурсии. Мы уже проделывали подобные вычисления в прошлой части. Это будет выражение с суммой геометрической прогрессии:

Отсюда, после суммирования, получится три варианта для итогового выражения: когда геометрическая прогрессия убывает; когда геометрическая прогрессия растет; когда прогрессия отсутствует, то есть множитель прогрессии 1.

В первом случае, имеем убывающую геометрическую прогрессию. Сумма прогрессии не превышает суммы бесконечной геометрической прогрессии с этим множителем, а та не больше константы, зависящей только от a,b,c. Константу можно вынести и останется только O(n^c)

А значит выражение (2) вырождается в

Второй случай, когда геометрическая прогрессия растет, уже подробно рассматривался в первой части на примере алгоритма Карацубы. Имеем сумму некоторого конечного числа элементов геометрической прогрессии, которые можем вычислить по формуле для суммы геометрической прогрессии. В итоге, обобщив ответ из части 1, мы получим формулу

Наконец, последний случай, когда прогрессия отсутствует. В этом случае в формуле (2) будут единицы под суммой, а сама сумма вырождается в выражение количества элементов суммы. В итоге получаем выражение

Применения

В комментариях к прошлой части были озвучены ряд алгоритмов, иллюстрирующие концепцию «Разделяй и властвуй». Самый простой случай, это Бинарный поиск. Известен еще с древних времен. Найти в отсортированном списке значение. Алгоритм общеизвестен. Но теперь рассмотрим его с точки зрения концепции «Разделяй и властвуй». Делим список [0,...,n] на два равных списка с индексами: [0,..., n/2–1], [n/2,....,n] Мы сравниваем искомое значение с максимальным значением из первого списка и определяем, лежит ли искомое значение в первом списке или во втором. Далее рекурсивно обходим список, уменьшенный вполовину, а на второй список не обращаем внимание.

То есть, мы делим проблему длины n, на a=1 одну проблему длины n/2, b=2. И на каждом уровне выполняем одну операцию сравнения за константное время O(1), c=0. Рекурсивное соотношение «Разделяй и властвуй» (1) для бинарного поиска выглядит так:

Т.е. a=1, b=2, c=0 и согласно мастер-теореме, это второй случай, где

И по мастер‑теореме мы получаем известную формулу сложности алгоритма бинарного поиска T(n)=O(log(n)).

Сортировка слиянием алгоритм эффективной сортировки. Список значений с индексам [0,...,n], который нужно отсортировать делим на два равных списка с индексами: [0,..., n/2–1], [n/2,....,n]. Рекурсивно сортируем каждый из меньших списков. Далее собираем итоговый список сливая два отсортированных списка.

Для расчета сложности алгоритма, сначала надо понять процедуру, которой можно слить два отсортированных списка в один отсортированный и какова ее сложность.Процедура выглядит так. Берем первый наименьший элемент из списка 1 и сравниваем его с первым наименьшим элементом из списка 2. Кто из них самый наименьший — поступает в итоговый слитый список и убирается из списка 1 или списка 2. Далее рекурсивно повторяем алгоритм для двух списков, один из которых на этом шаге стал меньше на один элемент.

На каждый рекурсивный вызов процедуры слияния происходит одно сравнение, т. е. действие сложности O(1). И таких действий, из описания рекурсии, будет n, где n сумма размеров первого и второго списка. Таким образом, процедура слияния будет иметь сложность O(n).

Теперь, определившись с алгоритмом, запишем рекуррентное соотношение (1) для мастер‑теоремы

Получается a=2, b=2, c=1 и согласно мастер теореме, это второй случай, где

И итоговое выражения для алгоритма сортировки слиянием

Умножение двух матриц

Если у нас есть две квадратные матрицы A и B размерностью n, то их произведением Z=AxB называют матрицу элементы которой равны

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

Тогда умножение двух матриц по наивному алгоритму с использование формулы выше сводится к вычислению n² элементов Z, каждое из которых является суммированием n произведений. т. е. итоговая сложность умножения получается O(n³). Казалось бы улучшить тут нечего. Но на помощь приходит «Разделяй и властвуй».

Если размерность матрицы n четная, то такие матрицы можно умножать блоками размерности n/2 по формуле

Если воспользоваться таким разбиением для «Разделяй и властвуй» то умножение двух матриц размерности n сводится к 8 произведениям матриц размерности n/2. После чего выполняется сложение этих матриц, что требует O(n²) операций для того, чтобы вычислить каждый из n² элементов итоговой матрицы.

Соотношение (1) в этом случае будет

Данное соотношение по мастер-теореме дает итоговую сложность O(n³), то есть никакого выигрыша в сравнении с наивным алгоритмом. Но вы уже догадываетесь, что как и при скалярном произведении, можно не делать все 8 произведений, а обойтись меньшим числом. И это действительно так, правда это не так тривиально, как в скалярном случае, но можно легко проверить, что соотношения верны. Достаточно выполнить 7 произведений матриц размерности n/2

Тогда произведения для формулы (3) можно получить используя только сложения и вычитания матриц P_1...P₇

Теперь у нас 7 произведений вместо 8. Рекуррентное соотношение будет

И итоговая сложность алгоритма умножения матриц будет

В третьей части посмотрим, как применяется «Разделяй и властвуй» к важным составляющим квантовых алгоритмов.