首页 > 代码库 > FFT 快速傅里叶变换

FFT 快速傅里叶变换

         这个东西很神奇,看了半天网上的解释和课件,研究了很长时间,算是大概明白了它的原理。

         话不多说先上图。

         技术分享

         我们要求的h(x)=f(x)*g(x),f(x)=Σai*x^i,g(x)=Σbi*x^i.

         朴素求复杂度是n2的,但一个x次多项式在平面上可以由x+1个点唯一插值表示,所以我们可以先用求出x+1个点(xi,f(xi))和(xi,g(xi)),再求出(xi,f(xi)*g(xi)),就可以反解出    h(x)的表达式。

         那么我们需要在nlogn的时间内干完这两步,首先xi的取值需要特殊取,令xi=ζ(n,i)(不懂复数的同学可以自行百度),令n(多项式次数,不够的话也要补)=2^m,那么

        技术分享

       未完待续。。。。

 

FFT 快速傅里叶变换