快速傅立叶变换(FFT)算法

已知多项式f(x)=a0+a1x+a2x2+...+am-1xm-1, g(x)=b0+b1x+b2x2+...+bn-1xn-1。利用卷积的蛮力算法,得到h(x)=f(x)g(x),这一过程的时间复杂度为O(n2)。但是,利用分治策略和插值法来求解h(x),可以将时间复杂度降低至O(nlogn),从而大幅提升算法的效率。此求值算法将被应用于FFT算法中。

一、多项式求值


首先,由lagrange插值法可以知道,对于一个n-1次多项式,只要给定n个不同的点(xi, yi),我们就可以计算出多项式的系数。因此,求解2n-1次多项式系数的问题,可以转化为多项式对1的复数域中所有2n次方根求值的问题。其中,1在复数域的2n次方根可以表示为

快速傅立叶变换(FFT)算法

设f(x),g(x)为n-1次多项式,则插值法求多项式h(x)=f(x)g(x)的系数的步骤如下:

  1. 选择2n个不同的值xj(j=0,1,...,2n-1),求出算f(xj),g(xj)
  2. 计算所有h(xj)=f(xj)g(xj)
  3. 由于h(x)的次数不高于2n-1,利用lagrange插值公式求出h(x)的系数

在第一步多项式求值过程中,如果用蛮力算法,即直接计算每一个A(wj),那么时间复杂度为O(n3)。但事实上,设Ak(x)=an-k+an-k+1x+...+an-1xk-1,则存在关系:

Ak(x)=an-k+xAk-1(x)

利用这一递推关系式来求解A(x)=An(x),复杂度可以降低到O(n2)。这比蛮力算法已经有了很大的改进,但有没有更高效的求值算法呢?

采用分治策略,可以将多项式求值过程的时间复杂度降低至O(nlogn),从而大幅提升算法的效率。这一算法的思想如下:

设要求值的多项式为A(x)=a0+a1x+...+an-1xn-1,不妨设n为偶数,令

A0(x)=a0+a2x+a4x2+...+an-2x(n-2)/2

A1(x)=a1+a3x+a5x2+...+an-1x(n-2)/2

A(x)=A0(x2)+xA1(x2)

值得注意的是,根据复数域2n次单位根的性质,x2并不需要重新计算,只要在单位圆上间隔取值就可以了。下面给出用分治策略为多项式求值的算法伪码

算法1 Polyval(A, W) //分治策略多项式求值(假设n为偶数)

输入:n-1次多项式A的系数a0,a1,...,an-1,以及w0,w1,...,w2n-1

输出:A(w0),A(w1),...,A(w2n-1)

1. if A的长度=1 return A(W)

2. else do

3.     计算W1: W[0]2,W[1]2,...,W[2n-1]2

4.     计算A0: A[0],A[2],...A[n-2]

5.     计算A1: A[1],A[3],...A[n-1]

6.     A0(W1)←Polyval(A0, W1)

7.     A1(W1)←Polyval(A1, W1)

8.     return A(W)=A0(W1)+WTA1(W1)

算法的递推方程为T(n) = 2T(n/2) + f(n), T(1) = O(1)。其中,f(n)为初始时计算所有2n次方根的时间,f(n) = O(n)。根据主定理,得到T(n) = O(nlogn)。

二、快速傅立叶变换


设f(x)=a0+a1x+a2x2+...+an-1xn-1, g(x)=b0+b1x+b2x2+...+bn-1xn-1,h(x)=f(x)g(x)。下面给出FFT算法的伪码:

算法2 FFT

1. 对x=wj(j=0,1,...,2n-1),分别计算f(wj),g(wj)

2. 利用步骤1的结果,计算所有dj=h(wj)

3. 构造多项式D(x)=d0+d1x+d2x2+...+d2n-1x2n-1

4. 对x=wj(j=0,1,...,2n-1),计算D(wj)

5. 设h(x)的系数为c0,c1,...,c2n-1,则有c0=D(1)/2n,c2n-1=D(w1)/2n,...,c1=D(w2n-1)/2n

不难分析,FFT算法时间复杂度为O(nlogn)。

上一篇:python闭包closure


下一篇:mysql参数配置文件