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

Алгоритм заснований на рекурсивному розділенні перетворення на кожному кроці на два шматки з розміром <math> N / 2</math>. Якщо <math>N</math> не ділиться на два, то робиться факторизація. Для розрахунку використовуються [[корені з одиниці]].

 

 

:<math>f_m = \sum_{k=0}^{2n-1} x_k \;e^{-\frac{2\pi i}{2n} mk }