О ВЕЩЕСТВЕННОЙ СЛОЖНОСТИ КОМПЛЕКСНОГО ДПФ

摘要

Приводится способ построения теоретически быстрого алгоритма вычисления дискретного преобразования Фурье (ДПФ) порядка N = 2~n. Показано, что ДПФ комплексного вектора длины N выполняется со сложностью асимптотически 3,76875 log_2N вещественных операций сложения, вычитания и скалярного умножения.