脚本宝典收集整理的这篇文章主要介绍了快速傅里叶变换(FFT) 学习笔记，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

背景

据说是高斯发明的

考虑从六年级开始学的多项式相乘,需要将所有项相乘并打开,时间复杂度(O(n^2)).FFT能在(O(nlogn))时间复杂度内解决这一问题.由于整数可以被拆成系数与进制幂之积的和,所以大整数乘法也可以用FFT加速.

表示法

一种显然的加速方式:在学习拉格朗日插值的过程中我们已经发现,n+1个点可以确定一个n次的多项式.所以两个n次多项式相乘可以通过取n+1次值,再把值乘起来的方式实现.显然有正确性.这样用n+1个点表示n次多项式的方法为点值表示法.

单位复根

现在考虑如何快速将系数表示法转化为点值表示法.我们在快速幂中已经学习了相关思想,即二进制拆分+分治/倍增.首先发现计算乘积非常浪费时间,如果能找到相乘始终为定制的数就可以加速这一过程.于是在复平面上选取单位圆,使复数 (omega) 满足 (omega^k=1) ,这样的复数称为复根(实际上是k等分圆周).又容易发现,对于n等分圆周产生的n个复根,只要知道第一个就可以将其他复根表示成它的幂次.我们用(omega_i^j)表示i等分圆周产生的第j个复根,显然有以下性质:(图:OI wiki)

快速傅里叶变换

将一个多项式奇偶分开,为了对称先将其补成(2^k)项.如:

奇偶分组可得:

设新函数(G(x)) , (H(x))

(f(x))表示为:

代入单位复根(omega^k_n):

代入(omega_n^{k+n/2}):

发现由(16)(17)两个式子套上(operatorname{DFT}),可以将(operatorname{DFT})中的n逐步化为1,从而求出结果.显然对于每个k分别代入即可.这样就在(O(nlogn))​的时间内求出了这个n-1次多项式的n组根(这里的n指的是补齐项之后的项数).

此外也可以将递归分治改为倍增,需要用到位逆序置换.

脚本宝典总结

以上是脚本宝典为你收集整理的快速傅里叶变换(FFT) 学习笔记全部内容，希望文章能够帮你解决快速傅里叶变换(FFT) 学习笔记所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。