О распараллеливании дискретного преобразования Фурье

Рассмотрен вопрос об асимптотической оценке временной сложности численного преобразования Фурье. Найдены условия, при которых известная оценка может быть достигнута. Показано, что в этих условиях противопоставление БПФ и ДПФ теряет смысл.