本文参考UCAS卜东波老师的计算机算法设计与分析课程撰写

前言

本文主要讲述分治思想在快速傅立叶变换（FFT）中的应用。快速傅立叶变换本质上属于多项式求值，将输入的n个复数$a_0,a_1,...,a_{n-1}$a0​,a1​,...,an−1​变换成n个复数$y_0,y_1,...y_{n-1}$y0​,y1​,...yn−1​。

快速傅立叶变换（FFT）

问题描述与分析

• 给定n个复数的数组$a_0,a_1,...,a_{n-1}$a0​,a1​,...,an−1​，求$A(x) = a_0+a_1+...+a_{n-1}x^{n-1}$A(x)=a0​+a1​+...+an−1​xn−1在n个特定点$1,\omega,\omega^2,...,\omega^{n-1}$1,ω,ω2,...,ωn−1的值，其中$\omega=e^{\frac{2\pi}{n}i}$ω=en2π​i,表n次单位复根

  将上述问题写成结果如下：
  $y_0 = a_0 + a_1+ ... +a_{n-1} \\ y_1 = a_0 + a_1\omega+...+a_{n-1}\omega^{n-1}\\ ...\\ y_{n-1} = a_0 + a_1\omega^{n-1}+...+a_{n-1}\omega^{(n-1)^2}$y0​=a0​+a1​+...+an−1​y1​=a0​+a1​ω+...+an−1​ωn−1...yn−1​=a0​+a1​ωn−1+...+an−1​ω(n−1)2
  考虑最简单的办法，对一个$y_i$yi​需要用一次for循环（包含n-1次加法和乘法），n个则复杂度为$O(n^2)$O(n2)，在分治思想（3）- 平面最近点对寻找问题（对点集归约）一文中也提到过，$O(n^2)$O(n2)在遇到n数据规模较大时就力不从心了，因此能否考虑通过分治来降低复杂度。

解决思路

首先观察多项式能进行分治的前提，对单位复根敏感的童鞋应该很容易知道其必然会周期性变化，这里有几个值需要知道$e^{i\pi}=-1,e^{2\pi}=1$eiπ=−1,e2π=1（依据复数的三角和指数形式对应即可），所以有$\omega^i=w^{n+i}$ωi=wn+i，可以发现上述多项式中有很多重复计算的地方，为了更明显的感受，我们举几个简单的例子。

• 当n=4时
  

  可以发现红色区域的内容相同，蓝色区域的内容相差一个$\omega^2$ω2
  因此我们只需要计算一半的内容即可。由于加法次数多于乘法，因此复杂度只需考虑加法使用的次数，本次计算耗时：$2（红色用两次加法）+ 2（蓝色用两次加法）+4（中间的4个加法）=4log_24$2（红色用两次加法）+2（蓝色用两次加法）+4（中间的4个加法）=4log2​4

• 当n=8时
  同样对于n=8的情景是类似的，由于数量过于庞大，这里沿用卜老师的图片
  
  其中，红色区域完全一样，蓝色区域差$\omega^4$ω4,再进一步我们可以发现红色区域其实就类似于n=4的情况，其左上与左下相同，右上与右下差$\omega^2$ω2，最终可以得到如下图（该图展示了整个分治计算的过程）
  

  其中，绿色区域覆盖全部，表示开始需要计算的内容，棕色区域只包含了上半部分的两块内容，在得到棕色区域结果后可以顺势得到下半部分的绿色区域，橙色区域包含上面1/4部分的两块区域，红色区域则值包含最上面一行的两块区域。 绿(要求)->棕(要求)->橙(要求)->红(解)->橙(解)->棕(解)->绿(解)，这是一个很明显的递归过程。

• 算法复杂度
  这个算法复杂度的计算也很容易，我们在每次划分的时候按照下标的奇偶性将数组分成两份，如n=8时，第一次递归，$a_0,a_2,a_4,a_6$a0​,a2​,a4​,a6​一组，$a_1,a_3,a_5,a_7$a1​,a3​,a5​,a7​一组，再进一步递归，$a_0,a_4$a0​,a4​一组，$a_2,a_6$a2​,a6​一组…而在计算得到各组的结果后将其线性求和（奇数部分要乘上$\omega^i$ωi系数），所用时间复杂度为$O(n)$O(n)(即中间的加法操作)，因此有
  $T(n) = 2T(\frac{n}{2})+O(n) = O(nlogn)$T(n)=2T(2n​)+O(n)=O(nlogn)

将上述过程转换为伪代码如下（由于伪代码中用到数学符号较多，因此借用书本内容）

逆快速傅立叶变换

所谓逆快速傅立叶变换，即傅立叶变换的反过程，即已知$y_0,y_1,...,y_{n-1}$y0​,y1​,...,yn−1​，求$a_0,a_1,...,a_{n-1}$a0​,a1​,...,an−1​，值得一提的是，FFT解决的是求值的问题（给定系数，求多项式的值），IFFT解决的是插值问题（给定多项式的值，求系数），将两者写成矩阵形式对比如下：

• FFT
  

• IFFT

本身是一个求逆的过程，由于范德蒙矩阵的特性，得到结果如下，$\overline{\omega}表示共轭$ω表示共轭

由此在原始伪代码基础上只需做些许变动即可，如下：

总结

这部分的内容主要阐述了分治思想在多项式计算上的应用，之所以能够分治，是因为我们发现了多项式计算中的冗余部分，这些重复计算内容可以被省略，且多项式的值可以被划分为奇偶两部分的特殊和，那么就可以递归地进行奇偶划分，由此使得计算的复杂度得到了降低。
这里总结一下依据该例得出的分治经验：

1. 先使用最直白的办法（通常复杂度是$O(n^2)$O(n2)或以上）
2. 找出算法计算的冗余部分（这一点很重要，如果没有发现冗余直接划分无法将计算的复杂度往下降）
3. 找出可以递归的入口（能够不断迭代往下进行），在多项式计算中是按照奇偶性进行递归
4. 考虑合并子问题解的额外开销，如果额外开销过大，则不适宜如此划分