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

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

К концу 50-х годов быстрое преобразование Фурье уже изобрели, но использовали только «по назначению»: для обработки сигналов, а не для умножения чисел.

В это время Андрей Колмогоров и несколько других пионеров информатики выдвинули «гипотезу \(n^2\)»: невозможно перемножить два \(n\)-значных числа, быстрее, чем за \(O(n^2)\). Основания на то были: шумеры научились умножать в «в столбик» (сложение \(n\) \(n\)-значных чисел) как минимум четыре тысячи лет назад, и за это время никто ничего быстрее не придумал.

На очередном научном семинаре с повесткой «давайте это уже докажем» один из его аспирантов неожиданно предъявил новый метод с оценкой сложности \(O(n^{\log_2 3})\), тем самым опровергая гипотезу. Аспиранта звали Анатолий Карацуба.

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

Алгоритм Карацубы основывается на парадигме «разделяй-и-властвуй». Чтобы понять, почему его асимптотика именно такая, нам понадобится более мощная теорема, которая говорит об асимптотике большого класса «разделяек».

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

\[ T(n) = \begin{cases} a T(\frac{n}{b}) + \Theta(n^c), & n > n_0 \\ \Theta(1), & n \leq n_0 \end{cases} \]

Тогда:



Доказательство. Рассмотрим «дерево рекурсии» этого соотношения. В нём будет \(log_b n\) уровней. На \(k\)-том уровне будет \(a^k\) вершин, каждая из которых будет стоить \((\frac{n}{b^k})^c\) операций. Просуммируем значения во всех вершинах по всем уровням:

\[ T(n) = \sum_{k=0}^{\log_b n} a^k (\frac{n}{b^k})^c = n^c \sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k \]

A. Если \(c > \log_b a\), то \(\sum (\frac{a}{b^с})^k\) это сумма убывающей геометрической прогрессии, которая не зависит от \(n\) и просто равна какой-то константе. Значит, \(T(n) = \Theta(n^c)\).

B. Если \(c = \log_b a\), то

\[ T(n) = n^c \sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k = n^c \sum_{k=0}^{\log_b n} 1^k = \Theta(n^c \log_b n) \]

C. Если \(c < \log_b a\), то так как сумма прогрессии асимптотически эквивалентна своему старшему элементу,

\[ T(n) = n^c \sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k = \Theta(n^c (\frac{a}{b^c})^{\log_b n}) = \Theta(n^c \cdot \frac{a^{\log_b n}}{n^c}) = \Theta(a^{\log_b n}) = \Theta(n^{\log_b a}) \]

Примечание. Для более точных оценок асимптотики «мерджа» теорема ничего не говорит. Например, если мердж занимает \(\Theta(n \log n)\) и задача разбивается каждый раз на две части, то асимптотика будет равна:

\[ \sum_{k=0}^{\log n} n \log \frac{n}{2^k} = \sum_{k=0}^{\log n} n (\log n - k) = n \sum_{k=0}^{\log n} k = \Theta (n \log^2 n) \]

В то же время эта рекуррента под условия теоремы не попадает. Можно лишь получить неточные границы \(\Omega (n \log n)\) и \(O(n^{1+\epsilon})\), если подставтиь \(c = 1\) и \(c = 1 + \epsilon\) соответственно. Заметим, что \(n \log n\) и \(n \log^2 n\) асимптотически меньше \(n^{1+\epsilon}\), каким бы маленьким \(\epsilon\) ни был.

Алгоритм Карацубы

Алгоритм Карацубы сводит задачу умножения двух чисел длины \(n\) к возведению \(n\)-значного числа в квадрат. Для простоты будем считать, что числа бинарные, а n = 2k является степенью двойки. На практике же лучше брать достаточно большое основание, а не двойку — \(10^9\), например.

Оказывается, что умножение и возведение в квадрат, вообще говоря, эквивалентные задачи: так как \(4ab=(a+b)^{2}-(a-b)^{2}\), то вместо умножения двух чисел \(a\) и \(b\) можно возвести два числа такого же порядка в квадрат и за линейное время сделать несколько сложений и вычитаний.

Итак, нам нужно возвести число x в квадрат. Разобьём его на две части, то есть представим в виде \(x = a + 2^k b\), где числа \(a\) и \(b\) являются \(k\)-значными. Внимание, алгебра:

\[ x^2 = (a + 2^k b)^2 = a^2 + 2^k ((a+b)^2 - a^2 - b^2) + b^2 \]

Выяснилось, что мы можем вместо возведения \(n\)-значного числа в квадрат возвести три \(\frac{n}{2}\)-значных значных числа в квадрат — \(a^2\), \(b^2\) и \((a+b)^2\) — и сделать константное количество сложений, вычитаний и сдвигов.

Пролистав пол-экрана выше, можно убедиться, что асимптотика будет \(\Theta (n^{\log_2 3}) \approx \Theta (n^{1.58})\): в данном случае наша задача разбивается на \(a = 3\) части в \(b = 2\) раз меньшего размера, а объединение происходит за \(O(n)\).

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

Развитие идеи

То же самое можно применить к матричному умножению — это называется алгоритмом Штрассена. В нём две матрицы разбиваются на \(8 = 4 + 4\) частей, перемножаются блочно, и сложной алгеброй от одного из 8 умножений получается избавиться, что даёт асимптотику \(O(n^{\log_7 8}) \approx O(n^{2.81})\).

И в алгоритме Штрассена, и в алгоритме Карацубы можно достичь и лучшей асимптотики, если разбивать объекты на большее число частей. Однако, на практике это не применяется, потому что константа получается слишком высокой.