S2 算法学习之FFT 初识2_s2算法

作者：2023面试高手 | 2024-02-25 04:29:59

踩

s2算法

1.FFT 的应用

（这章：主要围绕算法，实用性来讲，水平有限，请多指教）

答：1.FFT 进行 DFT 离散化

2.对DFT 进行奇偶分离（在这过程中，序号发生变化）

3.进行蝶形变化，得到值

4.对序号进行恢复

答： DFT 的复杂度是 N*n ,

理解：若有一个信号，怎么找到这个信号，比较，用1个信号和n个信号进行比较，1*n运算

若有N个信号，怎么找，用每一个跟N个信号进行比较，找到这个，再找下一个。 N*n 运算

FFT 的复杂度是 log2N

理解比较复杂：一个点分成奇偶两个函数来者计算，两次乘法，一次加法，一次减法

答： 蝶形变换是一种算法理解的图形表示。

理解如下：

对DFT原始函数进行分解后，奇偶分解，一个函数可以分成前后两个部分，只要知道一个点的前后两部分，就可以求出这个点的频率

如图示， x1(0) 和 X2（0） 才能共同推导出 X（0），注意第一行，和第五行绿线，共同求出X（0）

解：如图示

注意，分成奇偶后，怎么去计算？

式中： Feven[K] ,和 Fodd[K] 分为是一半数据，，k的取值应为：0，1，......，N/2-1

说明： Feven[K]用X1代替， Fodd[K]用X2代替

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/138643