Делить и властвовать: повышение эффективности алгоритмов. Часть 2

Отсюда, после суммирования, получится три варианта для итогового выражения: когда геометрическая прогрессия убывает; когда геометрическая прогрессия растет; когда прогрессия отсутствует, то есть множитель прогрессии 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. Рекуррентное соотношение будет

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

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