К концу 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}
$$
Тогда:
-
A. Если $c > \log_b a$, то $T(n) = \Theta(n^c)$.
-
B. Если $c = \log_b a$, то $T(n) = \Theta(n^c \log n)$.
-
C. Если $c < \log_b a$, то $T(n) = \Theta(n^{\log_b a})$.
Доказательство. Рассмотрим «дерево рекурсии» этого соотношения. В нём будет $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})$.
И в алгоритме Штрассена, и в алгоритме Карацубы можно достичь и лучшей асимптотики, если разбивать объекты на большее число частей. Однако, на практике это не применяется, потому что константа получается слишком высокой.
