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