Общий случай.

Пусть . Обозначим через матрицу перестановок порядка n, у которой положение 1 в i-ой строке определяется следующим образом. Число i запишем в виде , где и поместим единицу в позицию со столбцовым индексом j, где . Обозначим через диагональную матрицу i-ый элемент которой, равен .

Лемма 1. Справедливы равенства и .

Доказательство. Второе равенство получается из первого транспонированием обоих его частей, поэтому для доказательства леммы достаточно установить справедливость первого равенства. Переставим строки матрицы . Вначале расположим строки, номера которых делятся на , затем строки, номера которых делятся на с остатком 1, и так далее. Другими словами строку с номером ( ) переставим на место строки с номером . Выполнение указанной перестановки строк эквивалентно умножению матрицы слева на . Таким образом на пересечении строки и столбца j матрицы стоит элемент . Представим j в виде , где . Тогда . Из данного представления видно, что матрица имеет блочную структуру, а именно, она образована блоками порядка и на пересечении блочной строки и блочного столбца расположен блок . Эта же матрица получится при перемножении матриц и блочной матрицы, у которой на пересечении блочной строки и блочного столбца расположен блок . Последняя матрица разлагается в произведение матриц и . Тем самым установлено равенство , из которого вытекает утверждение леммы.

Следствие. Пусть известны алгоритмы, вычисляющие образы векторов при преобразованиях и с трудоемкостью и соответственно.

Тогда трудоемкость вычисления образа вектора преобразования по формулам леммы 1 не превосходит .

Доказательство. Трудоемкость вычисления образа вектора для матриц равна , - не более n, - и - n. Суммируя, получаем требуемое.

Во всех случаях, когда порядок дискретного преобразования Фурье разлагается в произведение не двух, а большего числа сомножителей, допускается многократное применение леммы 1. К тому же чем больше сомножителей, тем более эффективный алгоритм будет построен.

Следует отметить, что при многократном применении леммы 1 эффективнее матрицы перестановок умножать не сразу, а накапливать их произведение, и умножать на него в конце. При этом трудоемкость одной итерации снижается до (см. следствие леммы 1).

Теорема 1.Пусть . Тогда существует алгоритм вычисления образа вектора дискретного преобразования Фурье с трудоемкостью .

Доказательство. Применяя многократно лемму 1 и учитывая сделанное замечание о выполнении перестановок, получим, что трудоемкость метода равна . Считая , получаем трудоемкость всего метода (без умножения на матрицу перестановок) равна . Прибавив к полученной оценке трудоемкость умножения матрицы перестановок на вектор получим утверждение теоремы.

Следствие. Трудоемкость вычисления образа дискретного преобразования Фурье порядка n не превосходит величины если n - степень 2, если n -произведение степеней 2 или 3, если n – произведение степеней 2,3,5.