50. Преобразование Фурье

Дискретное преобразование Фурье трансформирует последовательность комплексных (либо вещественных) чисел xn  в последовательность комплексных чисел Xn . Прямое и обратное преобразования Фурье определяются, как:

Приведенные выше формулы имеют сложность O(N 2), однако широко известен способ снизить сложность дискретного преобразования Фурье доO(N·log(N)). Быстрое преобразование Фурье широко используется как само по себе, так и для ускорения вычисления других преобразований - быстрого вычисления свертки и кросс-корреляции.