Изменения
Нет описания правки
{{Определение
|definition=
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (, FFT)'') {{---}} это метод, позволяющий вычислять [[Дискретное преобразование Фурье | дискретное преобразование Фурье ]] за время <tex>O(nlognn \log n)</tex>.
}}
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>DFT(A_0)</tex> и <tex>DFT(A_1)</tex> за линейное время вычислить <tex>DFT(A)</tex>. Так как здесь используется идея "разделяй и властвуй", то асимптотическая оценка будет <tex>O(nlognn \log n)</tex>.
Пусть <tex>DFT(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}</tex> и <tex>\mathrm{DFT}(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}</tex>. Найдем вектор значений <tex>\mathrm{DFT}(A) = \{y_k\}^{n-1}_{k=0}</tex>.
* Из <tex>(1)</tex> получаем значения для первой половины коэффициентов:
<center><tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex></center>
