Карацуба
Постановка задачи
Есть два многочлена $A$ и $B$ степени $2^n$. Необходимо найти их произведение.
Решение в лоб, используя идею разделяй и властвуй
Представим $A = x^\frac{n}{2} \cdot P_A + Q_A$ и $B = x^\frac{n}{2} P_B + Q_B$. Тогда $AB = (x^\frac{n}{2} P_A + Q_A)(x^\frac{n}{2} \cdot P_B + Q_B)=x^n P_A P_B + x^\frac{n}{2}(P_A Q_B + P_B Q_A) + Q_A Q_B$.
Здесь все действия делаются за линию, кроме умножения многочленов. Чтобы перемножить многочлены степени $2^\frac{n}{2}$ запустим наш алгоритм рекурсивно. Будет 4 запуска от многочленов в два раза меньшей длины.
Время работы такого алгоритма получится $T(n) = 4T(\frac{n}{2}) + O(2^n)$, что равняется $O(2^{2n})$ и ничем не лучше обычного перемножения в два цикла.
Алгоритм Карацубы
Оказывается в предыдущем алгоритме можно обойтись всего тремя рекурсивными запусками. Действительно $P_A Q_B + P_B Q_A = (P_A + Q_A)(P_B + Q_B) - P_A P_B - Q_A Q_B$. Первые два рекурсивных запуска мы тратим на вычисление $P_A P_B$ и $Q_A Q_B$, после чего для получения $P_A Q_B + P_B Q_A$ достаточно вычислить (P_A + Q_A)(P_B + Q_B), что можно сделать за одно умножение вместо двух.
Время работы данного алгоритма будет выражаться как $T(n) = 3T(\frac{n}{2}) + O(2^n)$, что равняется $2^{n\log_2(3)}$
Автор конспекта: Станислав Донской
По всем вопросам пишите в telegram @stasana