Виды преобразования Фурье

[g_coder]

Насколько я знаю, помимо обычного преобразования Фурье существуют еще быстрое, дискретное и оконное преобразования Фурье. В обычном я худо-бедно разобрался.
Если не трудно, объясните как можно проще основные особенности каждого из видов.

[Pphantom]

Вообще-то это неудачная классификация, вроде того, что предметы бывают зелеными, красными, длинными и тяжелыми.

"Обычное" - стандартное интегральное преобразование. Дискретное - запись интегрального преобразования в виде суммы для дискретного набора данных. Быстрое - алгоритм, позволяющий выполнить дискретное преобразование для некоторого набора данных. Оконное преобразование Фурье - строго говоря, вообще не преобразование Фурье (или, если угодно, обобщение преобразования Фурье, последнее получается в частном случае, когда функция окна - константа). Соответственно, оконное преобразование также можно представить в дискретном виде.

[Maslov]

С именем Фурье связано по меньшей мере 4 преобразования (с соответствующими обратными):

непрерывный сигнал в непрерывный спектр - интегральное преобразование Фурье
непрерывный сигнал в дискретный спектр - разложение в ряд Фурье
дискретный сигнал в непрерывный спектр - Discrete-time Fourier transform
дискретный сигнал в дискретный спектр - дискретное преобразование Фурье

Вычисление ДПФ "в лоб" по формуле

$X_k = \sum \limits_{n=0}^{N-1}x_n e^{-i 2\pi k n / N }$

требует порядка $O(N^2)$ операций; быстрое преобразование Фурье -- это алгоритм вычисления ДПФ, требующий менее $O(N^2)$ операций (обычно порядка $O(N \log N)$).