FFT快速傅立叶变换

//最近突然发现博客园支持 $\LaTeX$ ，非常高兴啊！

话说离省选只有不到五天了还在学新东西确实有点逗……

切到正题，FFT还是非常神奇的一个东西，能够反直觉地把两个多项式相乘的时间复杂度降到 $O(n \log n)$ 。

首先，多项式的表示方法有两种：

　　第一种是系数表示法 $\sum_{i=0}^{n-1}a_i x^i$ ，就是正常的表达一个多项式的办法。

　　第二种比较神奇，是点值表示法，就是用 $n$ 个点 $(x_i,y_i)$ 来表示一个多项式，也就是用两个列向量 $x$ 和 $y$ 来表示一个多项式。

将两个多项式表示成系数表示法直接相乘需要 $O(n^2)$ 的时间，而将两个用点值表示法的多项式相乘却只用 $O(n)$ 的时间（将两个多项式的 $y$ 向量的每一维分别相乘即可）。

而FFT干的事情就是在 $O(n\log n)$ 的时间内将多项式从系数表示法转化成点值表示法，或者是将点值表示法转化为系数表示法。

从直觉上看，列向量 $x$ 的每一维的随便乱取显然是不靠谱的，为了保证优越的复杂度，我们引入一个神奇的工具——单位复根。

================未完待续================

FFT快速傅立叶变换,布布扣,bubuko.com

FFT快速傅立叶变换

原文：http://www.cnblogs.com/zhuohan123/p/3619567.html