Изменения

'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform (, DFT)'') {{---}} многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:

'''Обратное дискретное преобразование Фурье''' (англ. ''Inverse DFT'') для вектора значений многочлена <tex>A(\omega_n)</tex> <tex>(y_0, y_1, \ldots , y_{n-1})</tex> {{---}} это вектор коэффициентов этого многочлена <tex>(a_0, a_1, \ldots , a_{n-1})</tex>:

\mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).

A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTF}(B)).

Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(nnlogn)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].

|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>|proof= '''Доказательство:''' 

\mathrm{DFT}(a_0, a_1, a_{n-1}) = \mathrm{InvDFT}(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1))

Посчитаем <tex>\mathrm{DFT}</tex> для полинома степени <tex>n = 4</tex>.

== Источники информации ==

[[Категория: Дискретная математика и алгоритмыАналитическая теория чисел]]