Быстрое преобразование Фурье

---

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем ${\displaystyle O(N^{2})}$ (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность ${\displaystyle O(N\log(N))}$.

Алгоритм применим к любым коммутативным ассоциативным кольцам с единицей, чаще применяют к полю комплексных чисел (c ${\displaystyle \varepsilon =e^{2\pi i/n}}$) и к кольцам вычетов (которым, в частности, является компьютерный целый тип).

При применении основного алгоритма дискретное преобразование Фурье может быть выполнено за ${\textstyle O(N(p_{1}+\cdots +p_{n}))}$ действий при ${\textstyle N=p_{1}p_{2}\cdots p_{n}}$, в частности, при ${\displaystyle N=2^{n}}$ понадобится ${\displaystyle O(N\log(N))}$ действий.

---