历经两天，总算搞定了2基快速傅里叶变换FFT
2016-04-27 21:15阅读：
结构动力学里提到了时域到频域的傅里叶变换，但老师只是一笔带过说这个太难我们就不要求掌握，因此之前的动力学时程求解都是在时域范围内，这次由于需要求时程的傅里叶谱，因此找了一些资料看，想学习一下傅里叶变换，下面简单说一下心得：
傅里叶变换分为三种，
解析解：即连续傅里叶变换，包括时域到频域的正变换和对应的逆变换：
这种解法只适用于理论分析，要用于数值计算不可能实现，因此有了第二种，就是对连续傅里叶变换做近似的离散傅里叶变换，如下：
离散傅里叶变换理论上可用于数值计算，可其计算量随着计算李三点数的增多成指数增长，时间复杂度大，计算代价较高，因此用于大量时程计算的时候也不适用
于是这两天硬着头皮看了关于时域抽基2快速傅里叶变换FFT的原理，今天总算把它搞懂并实现了出来（其实MATLAB中已经给了现成的算法，即调用FFT函数，我还自己把整个过程公式推了一遍，真是强迫症害死人），然而因为要自己处理一大批数据，因此只能用别的方法实现，这里用的是CSharp,
简单介绍一下FFT吧
即利用三角函数的周期性和欧拉公式，把N项数据的序列抽样成N个时间序列，（N必须为2的整数次幂），然后利用蝶形算法，就能使整个过程的计算量大大减小。
计算公式如下：
看着这一大堆公式就感觉有点复杂，何况还要结合蝶形算法，一开始真是有点蒙逼（大一没学过傅里叶变换的孩子伤不起啊），想到还要实现出来真是有点崩溃，然而功夫不负有心人，花了一天的时间，总算搞明白了（若需要源码请私信我）：
搞定了还是挺有成就感的，继续加油努力！
