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

Определение: преобразование набора значений функции (y₀…y_n-1) в набор коэффициентов (A₀…A_n-1) (используя (4.18б)), участвующих в разложении Фурье, называется прямым преобразованием Фурье (ППФ), а обратным преобразованием Фурье (ОПФ) – преобразование массива A_j в y_k (по (4.18б)).

Если осуществлять эти вычисления непосредственно по (4.18а, б), то трудоёмкость - (т.к. имеем n коэффициентов, в каждом из которых n слагаемых).

Эти же вычисления можно делать по более быстрым формулам – быстрое преобразование Фурье. Трудоёмкость по этим формулам существенно меньше: не , а .