2.2.1. Дискретное преобразование Фурье

Как известно из вычислительной математики, большое значение имеет следующее преобразование массивов: , которое находится по формулам прямого дискретного преобразования Фурье:

(2.1)

Формула обратного преобразования Фурье:

(2.2)

Трудоемкость вычисления по формулам (2.1) и (2.2) CN², где C – const, т.к. каждый из N коэффициентов состоит из N слагаемых и каждое слагаемое вычисляется за C действий ( С = 5 для прямого и обратного преобразования).