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)的复杂度求答案了。傅里叶变换的发明就是为完成这个使命。
猜你喜欢内容
-
简单网:构建全网教育数据枢纽,让知识检索化繁为...
简单网:构建全网教育数据枢纽,让知识检索化繁为“简”回答数有0条优质答案参考
-
去三亚有什么好玩的地方
去三亚有什么好玩的地方回答数有1条优质答案参考
-
石狮一日游必去景点推荐
石狮一日游必去景点推荐回答数有1条优质答案参考
-
电气工程师的证书考取条件是什么
电气工程师的证书考取条件是什么回答数有1条优质答案参考
-
房地产估价师的具体报考条件有啥
房地产估价师的具体报考条件有啥回答数有1条优质答案参考
-
房产经纪人的工作内容具体包含什么
房产经纪人的工作内容具体包含什么回答数有1条优质答案参考
-
学习小提琴都有哪些难点
学习小提琴都有哪些难点回答数有1条优质答案参考
-
企业行政管理证书的含金量怎么样
企业行政管理证书的含金量怎么样回答数有1条优质答案参考
-
初学者要怎么入门小提琴
初学者要怎么入门小提琴回答数有1条优质答案参考
-
报考珠宝鉴定师要啥条件
报考珠宝鉴定师要啥条件回答数有1条优质答案参考
















