Прием «разделяй и властвуй

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

Проиллюстрируем данный подход на примере умножения чисел и , имеющих одинаковую длину n. Положим . Представим число a в виде , где и . Аналогично представим число b в виде , где и . Произведение чисел a и b равно . Вычисление произведения чисел a и b по этим формулам потребует выполнения четырех произведений чисел длины k, трех операции сложения с числами длины n и сдвигов на k и 2k ячеек. Наиболее трудоемкими среди перечисленных операций являются операции умножения. Следовательно, желательно заменить более «трудоемкую» операцию умножения менее «трудоемкими» операциями.

В нашем случае можно поступить следующим образом. Заменить задачу умножения чисел a и b на задачу умножения двучленов и , с последующим вычислением значение полученного квадратного трехчлена в точке . Квадратный трехчлен полностью определяется своими значениями в трех точках. Например, при подстановке x=-1,0,1 получим систему . Положим , , . Тогда , , . Таким образом, при вычислении коэффициентов квадратного трехчлена потребуется выполнить три операции умножения с числами длины k, шесть операций сложений (вычитаний) и две операции деления на 2. Для вычислений произведения чисел a и b потребуется провести ещё операции сдвига и сложения.

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

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

Обозначим через трудоемкость умножения чисел длины n этим алгоритмом. Из сказанного выше, следует равенство (справедливое при ). Рассмотрим случай, когда является степенью двойки. После многократного применения рекуррентного соотношения получим , где s удовлетворяет неравенствам , ( или, что тоже самое ). Свернув сумму по формуле суммы членов геометрической прогрессии, выводим равенство , учитывая ограничения на s получаем неравенство . После несложных преобразований правой части неравенства получаем , где .

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