Introduction to FFT¶
中文互联网中讲解 FFT 博客的作者大致分为两类：一类人大概是信号人，另一类人是 OI （信息竞赛）人。这两种博客往往内容其实没有太大的交集，虽然讲解的是同一个算法。
在我高中时期学习这个算法的时候就感到非常非常的困惑，因为我无法理解为什么上来就要代入一些特殊的点，也无法理解为什么逆变换和正变换这么的类似。更令人迷惑的是当你试图查找一些资料，大部分傅里叶变换的讲解都在讲时域、频域等等没听说过的事情，搞不懂到底这两者之间有什么联系。
也有过很多人问我或是交流这两者之间的关系，为了更好的阐述，我们写一篇博客（其实主要是防止自己再一次忘掉，我已经数不清忘掉多少次了）。
历史¶
热方程¶
为了更好的理解，我们先从历史说起。
在傅里叶之前欧拉就已经用三角函数的级数来解决一些弦振动问题了，但是傅里叶第一个提交论文声明:
任何周期函数都可以表示成三角函数的级数
当时大部人并不接受这种说法，因为它并没有很严格的证明。事实上这个结论也确实是错的，但在实际应用中大多数情况都满足 Dirichlet 条件（一个傅里叶变换存在的充分不必要条件），所以它依然是一个很强大实用的工具。
最早这个工具被傅里叶用来解决热方程，一种极其重要的偏微分方程：
这个式子中 \(u\) 代表温度，\(t\) 代表时间，\(x\) 代表坐标。式子左边是温度随时间的变化，右侧可以理解为一个点和周围点温度的差的大小。大概意思是说如果你比周围的人热的多，那你温度就会快速的下降。
我们发现如果我们让 \(t=0\) 时初始条件的 \(u\) 为正余弦函数，那么这个方程将非常容易求解；同时这里的算符都满足线性性，所以一些三角函数的叠加也是简单的。
那如果我们能让现实里的 \(u_{t=0}\) 分解成一系列三角函数，事情就简单了。
信号与系统¶
满足线性性的系统还有很多，除了微分方程的解之外还有信号里的 LTI 系统。
此时傅里叶变换可以被理解为从时域（一个波，横坐标是时间，纵坐标是振幅）到频域（把一个波分解成若干个正余弦波，此时一个波可以表示为横坐标是频率，纵坐标是对应频率分量的强度）的变换。
快速乘法¶
讲了这么多，到底和快速乘法有什么关系？
后面我们会介绍到原域的卷积（乘积）对应傅里叶变换后的域上的乘积（卷积）。
而我们注意到乘法本身可以看成是各位数字的卷积，所以如果我们有一种可以快速求傅里叶变换的操作，那真是太棒了。我们可以先快速傅里叶变换，再对变换后的函数逐点乘积，最后再变换回去。这样做的好处是直接求卷积复杂度很高，而逐点乘积就简单多了。
快速傅里叶变换¶
历史上有很多人重新发明过很多次傅里叶变换，大家一般认为最早是高斯发现了这个算法，但通用的算法是 James Cooley 和 John Tukey 发明的，他们分析了算法的复杂度是 \(O(n\log n)\).
但是这篇文章和傅里叶的文章据说因为写的非常晦涩，所以大家一开始也看不懂。所以我们学起来很费劲也是有道理的 ：）
缘起 - 无穷维向量空间¶
在高中数学中，我们应该学习了欧氏空间的向量和内积。实际上内积这个概念可以推广到很多空间，比如这里我们考虑函数空间。
对于复函数空间，我们可以定义内积为：
这里 \(\bar{\cdot}\)