fft的c语言实现,fft编程c

大家好，今天小编关注到一个比较有意思的话题，就是关于fft的c语言实现的问题，于是小编就整理了1个相关介绍fft的c语言实现的解答，让我们一起看看吧。

1. c语言实现fft实验原理？

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)的复杂度求答案了。傅里叶变换的发明就是为完成这个使命。

到此，以上就是小编对于fft的c语言实现的问题就介绍到这了，希望介绍关于fft的c语言实现的1点解答对大家有用。

标签： 多项式 复杂度 乘法