1
правка
Изменения
→Алгоритм построения БПФ
== Алгоритм построения БПФ ==
Пусть имеется многочлен <tex>A(x)</tex> степени порядка <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.
<center><tex> A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} </tex></center>
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>\mathrm{DFT}(A_0)</tex> и <tex>\mathrm{DFT}(A_1)</tex> за линейное время вычислить <tex>\mathrm{DFT}(A)</tex>. Так как здесь используется идея "''разделяй и властвуй"'', то асимптотическая оценка будет <tex>O(n \log n)</tex>.
Пусть <tex>\mathrm{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>.
*[[Дискретное преобразование Фурье]]
== Источники информации ==
*[https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Википедия {{---}} Быстрое преобразование Фурье]
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Дискретная математика Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмытеории чисел]]
