О вещественной сложности комплексного ДПФ

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