2.3.2. Обычный и быстрый алгоритм свертки

Рассмотрим два конечных вектора (массива). Для удобства их длина одинакова и равна n. Если же массивы имеют разное количество элементов n и m, причем n>m, то более короткий массив дополняем n-m нулями до n элементов (выравниваем массивы по более длинному).

Имеем:

a = (a₀, a₁, a₂, …, a_n-1)

b = (b₀, b₁, b₂, …, b_n-1).

Оценим трудоемкость вычисление свертки по обычному алгоритму:

c₀ = a₀b₀ - состоит из 1 слагаемого

c₁ = a₀b₁ + a₁b₀ - состоит из 2 слагаемых

c₂ = … - состоит из 3 слагаемых

до середины массива с количество слагаемых, из которых состоят его элементы, увеличивается до n

с_n-1 = a₀b_n-1 + … + a_n-1b₀,

n слагаемых

а от c_n до c_2n-2 уменьшается. Последний элемент массива – c_{2n – 2} – имеет одно слагаемое. Итого:

T(n) = 1 + 2 + 3 + … + (n-1) + n + (n-1) + … + 3 + 2 + 1 = n².

Если реализовать вычисления по формуле (2.5а), т.е. нерационально – путем организации трех вложенных циклов (во внутреннем цикле будет проверка по условию k + l = i), то трудоемкость будет даже не n², а n³. На самом деле, используя в формулах свертки преобразование Фурье, можно снизить трудоемкость с n² до nlog(n). Для вывода этих формул сначала докажем теорему.

Теорема 2.1. Пусть a = (a₀, a₁, a₂, … , a_n-1, 0, 0, 0 … 0)

и b = (b₀, b₁, b₂, … , b_n-1, 0, 0, 0 … 0) – массив длины 2n полученные из первоначальных массивов длины n путем дописывания n нулей. Соответственно, F(a) и F(b) – преобразования Фурье от этих массивов, т.е.

F(a) =

F(b) =( .

Тогда преобразование Фурье от их свертки:

есть ничто иное, как покоординатное произведение массивов F(a) и F(b), помноженное на 2n: .

Доказательство. Введем переменную w = exp { -2i/2n}.

Тогда, по формулам преобразования Фурье:

Аналогично,

Теперь мы можем перемножить и . Посмотрим, что получится в результате:

Ввёдем новую переменную m = l +j.

В результате получаем

Теорема доказана.

Используя Теорему 2.1, в которой фактически сказано, что преобразование Фурье от свертки есть

F(c) = F(a*b) = 2n F(a) ○ F(b)

Операция покоординатного перемножения массивов

приходим к выводу, что можно выполнять свертку с помощью преобразования Фурье по следующей формуле:

a*b = F^-1(2nF(a) ○ F(b)), (2.6)

где F^-1 – обратное преобразование Фурье. => Свертка массивов a и b может быть выполнена по формуле 2.6.

Трудоемкость свертки по формуле 2.6:

T(n) = 3 · 2n · log(2n) ≈ n logn << n²

т.к. в расчетах применяются 2 прямых и одно обратно преобразование Фурье с одинаковой трудоемкостью 2nlog(2n), и длина обрабатываемого массива 2n

трудоемкость покоординатного перемножения массивов