Швидке перетворення Фур'є: відмінності між версіями

'''Швидке перетворення Фур'є''' (часто '''FFT''' від {{lang-en|Fast Fourier Transform}}) -— швидкий [[алгоритм]] обчислення [[Дискретне перетворення Фур'є|дискретного перетворення Фур'є]]. Якщо для прямого обчислення дискретного перетворення Фур'є з ''N'' точок даних потрібно [[Нотація Ландау|O(''N'' ²)]] арифметичних операцій, то FFT дозволяє обчислити такий самий результат використовуючи O(''N'' log ''N'') операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон.