全站数据
8 4 2 0 5 8 1

c语言实现fft实验原理

考研一姐 | 简单学习,快乐成才!         
问题更新日期:2024-10-15 14:05:36

问题描述

c语言实现fft实验原理,在线求解答
精选答案
最佳答案

FFT可以用来加速多项式乘法。假设有两个n−1次多项式A(x)和B(x),我们的目标是——把它们乘起来。

普通的多项式乘法的复杂度是O(n2)的,我们要枚举A(x)中的每一项,分别与B(x)中的每一项相乘,来得到一个新的多项式C(x)。

但是,如果A(x),B(x)两个多项式用点值表示的方法进行相乘,复杂度是O(n)的。具体方法:C(xi)=A(xi)×B(xi),所以枚举xi即可。

要是我们把两个多项式转换成点值表示,再相乘,再把新的点值表示转换成多项式岂不就可以O(n)的复杂度来解决多项式乘法了!

显然,把多项式转换成点值表示的朴素算法是O ( n 2 ) O(n^2)O(n 2 )的。难道大整数乘法就只能是O ( n 2 ) O(n^2)O(n 2 )吗?不甘心的同学可以发现,大整数乘法复杂度的瓶颈可能在“多项式转换成点值表示”这一步做改进,只要完成这一步就可以O(n)的复杂度求答案了。傅里叶变换的发明就是为完成这个使命。