MIT6.046算法设计 L3 快速傅里叶变换(分治思想) 学习笔记

warning
这是一篇不求甚解的笔记(因为作者太菜),只是大概的粗略的了解了一下快速傅里叶变换的的分治思想
你看这篇文章并不能让你学会FFT!
这篇笔记真的很水!

推荐视频:
快速傅里叶变换(FFT)——有史以来最巧妙的算法？

导入

对于一个多项式A(x)=a0+a1x+a2x^2+…+a(n-1)x^(n-1)

其有多少种不同的表示方式

  1. 系数表达
    可以将多项式抽象为一个向量(a0,a1,a2,a3,…an−1); 每个向量都与一个多项式一一对应

  2. 点值表达,对于一个多项式,给定n个数值x0,x1,….,x(n-1)带入A(x)即可确定一个n-1项的多项式

    n个点可以确定一个n-1的多项式

  3. 加法式?
    image-20231016112119135

多项式不同表达方法对多项式计算的时间复杂度

image-20231016112413080

如何获取最佳的多项式运算的时间复杂度?

从上图中我们可以看出,系数表达式的乘法较为复杂,而点值表达的求值运算比较复杂
有没有一种方法,能让系数表达方法和点值表达方法之间相互转换,让所有运算都能在O(n)时间复杂度内完成?

快速傅里叶变换 FFT

如果我们需要求两个多项式的乘积

image-20231016115416131

比如Ax,Bx都是2阶的多项式,他们的乘积C则为4阶多项式,需要5个点来确定; 我们从AB各取x相同的5个点,然后把他们相乘,带入C,就能求出C了

通过这样的计算,计算多项式乘法的时间一下从O(n^2)缩短为O(n)

怎么取点更快更好?

多项式可以拆成两个子式子嘛,一个奇一个偶,都只需要求x的正或负半轴就能知道另外半边的值,这样计算量又少了一半
所以我们需要做的是,把多项式拆成奇偶两部分,对他们分开计算,然后再合并求值,计算出他们相乘后得到的新的多项式就行

还能更好吗??

我们知道,对一个数a开方得到数b,b^2显然等于a

如果重复上面的分奇偶的部分,就差不多是不断地找平方根x

这里要引入一个单位根的概念

image-20231016120326592

image-20231016120418280

傅里叶算法

FFT算法的输入是多项式的n个系数其中n是2的幂次，我们取为1的n次方根，递归的底层情况是n=1，此时我们只在一个点上求多项式的值。

img

递归的主要命令就是把多项式拆分成奇/偶函数两部分，两部分就是调用函数两次，此时这两个子多项式函数都是n/2阶的，所以对应的求值点将是1的n/2次方根。