头部背景图片
Decaku 's Blog |
Decaku 's Blog |

快速傅里叶变换学习笔记

$ 学了几遍的FFT,以前似乎都没有彻底弄懂,这次 \\
应该是稍微会点了。$


什么是快速傅里叶变换

$ 快速傅里叶变换(FFT)是一种能在O(nlogn)时间内完成多项式转点值表达式的算法 \ $


多项式的点值表达式

  • $ 点值表达式:设A(x)是一个n-1次多项式,显然用n个不同的点可以 \\
    唯一确定A(x),设出方程组以后解出系数即可,多项式点值表达即 \\
    n个不同的点。 \ $

  • $ 求值:把多项式转换成点值表达式,需要带入n个不同的点求出对应 \\
    n个y,这部分复杂度是O(n^{2})的。 \ $

  • $ 插值: 即把多项式的点值表达式转换成系数表达式,朴素的多项 \\
    式插值算法是O(n^{2})的,这里不再赘述。 \ $


多项式乘法

$ 设有两个多项式A(x)和B(x),把两个多项式相乘得到多项式C(x),\\
朴素的做法复杂度是O(n^{2})的,我们需要枚举每一项相乘。 \\
但有趣的是,多项式的点值表达式乘法却是O(n)的,\\
因为C(x_i)=A(x_i)*B(x_i),所以我们对A(x)和B(x)求值以后, \\
对它们点值做乘法,再插值回去就可以得到C(x)的系数表达式了。\\
我们发现多项式乘法的时间复杂度瓶颈在求值和插值上。$


离散傅里叶变换

$ 按照之前所讲,求点值表达时自变量是可以任选的,但是离散傅里叶变换 \\
中的n个自变量是一个复平面上的单位圆周上的n等分点,这里为什么要这么 \\
选择自变量我下面会讲。首先来普及一些复数的性质。 \ $

  • $我们设这n个点从x轴正半轴开始,逆时针以此编号为0到n-1,设第k个点对应的 \\
    虚数为\omega_{n}^{k},其对应的向量应该是(cos\frac{n}{k}2\pi,sin\frac{n}{k}2\pi), \\
    也就是说这个复数是cos\frac{n}{k}2\pi+i*sin\frac{n}{k}2\pi。 \\$

  • $\omega_{n}^{k}=\omega_{2n}^{2k}。把单位圆n等分取第k份等价于把单位圆2n等分取第2k份。 \\$

  • $\omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^{k}。两个点关于原点对称,向量等值反向。 \\$

重要结论 $把多项式A(x)的求值结果作为系数构造另一个多项式B(x),再把n个单位根的倒数\\
\omega_{n}^{0},\omega_{n}^{-1}…\omega_{n}^{1-n}带入B(x)求值,得到的每个数再除以n ,就是A(x)的各项系数了,\\
这样做实现了把插值变成了求值,这也是为什么我们选择单位复根的原因,\\
具体证明以后再填坑了。$


快速傅里叶变换

$ 尽管离散傅里叶变换实现了把插值变成求值,但求值的时候复杂度仍然是O(n^{2})的, \\
于是快速傅里叶变换应运而生了,它是一种分治的傅里叶变换。 \\
我们设A(x)=a_0+a_{1}x+…+a_{n-1}x^{n-1} \ 考虑把A(x)的每一项按照下标的奇偶 \\
分成两部分: \ A(x)=(a_0+a_{2}x^{2}+…+a_{n-2}x^{n-2})+(a_1x+ \ a_3x^3+…+a_{n-1}x^{n-1}) \\
设两个多项式: \\A_1(x)=a_0+a_2x+…+a_{n-2}x^{\frac{n}{2}-1} \\
A_2(x)=a_1+a_3x+…+a_{n-1}x^{\frac{n}{2}-1} \\
则A(x)=A_1(x^2)+xA_2(x^2) \\
假设k<\frac{n}{2},现在要把x=\omega_n^k带入 \\
A(\omega_n^k)=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k}) \\
=A_1(\omega_{\frac{n}{2}}^k)+\omega_n^kA_2(\omega_{\frac{n}{2}}^k) \\
那么对于A(\omega_n^{k+\frac{n}{2}}) \\
有A(\omega_n^{k+\frac{n}{2}})=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}A_2(\omega_n^{2k+n}) \\
=A_1(\omega_{\frac{n}{2}}^k * \omega_n^n)+\omega_n^{k+\frac{n}{2}}A_2(\omega_{\frac{n}{2}}^k * \omega_n^n) \\
=A_1(\omega_{\frac{n}{2}}^k)-\omega_n^{k}A_2(\omega_{\frac{n}{2}}^k) \\
所以,当我们知道两个多项式A_1(x)和A_2(x)分别在(\omega_{\frac{n}{2}}^0,…\omega_{\frac{n}{2}}^{\frac{n}{2}-1})的 \\
点值表示,就可以O(n)求出A(x)在(\omega_n^0,…\omega_n^{n-1})处的点值表示。 \\
每次递归问题规模减小一般,分治边界为n=1。$


快速傅里叶变换的优化

$ 有几点优化,一种是递归转非递归形式,一种是蝴蝶操作,这里暂时先咕了,有空再更新。 $

avatar Decaku 菜菜菜