首页 > 代码库 > 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 快速傅里叶变换
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。