Изменения
→Алгоритм построения БПФ
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <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>.
