快速傅里葉變換

快速傅里葉變換（英語(yǔ)：Fast Fourier Transform, FFT），是快速計(jì)算序列的離散傅里葉變換（DFT）或其逆變換的方法。傅里葉分析將信號(hào)從原始域（通常是時(shí)間或空間）轉(zhuǎn)換到頻域的表示或者逆過(guò)來(lái)轉(zhuǎn)換。FFT會(huì)通過(guò)把DFT矩陣分解為稀疏（大多為零）因子之積來(lái)快速計(jì)算此類變換。?因此，它能夠?qū)⒂?jì)算DFT的復(fù)雜度從只用DFT定義計(jì)算需要的??，降低到??，其中???為數(shù)據(jù)大小。

快速傅里葉變換廣泛的應(yīng)用于工程、科學(xué)和數(shù)學(xué)領(lǐng)域。這里的基本思想在1965年才得到普及，但早在1805年就已推導(dǎo)出來(lái)。?1994年美國(guó)數(shù)學(xué)家吉爾伯特·斯特朗把FFT描述為“我們一生中最重要的數(shù)值算法”，它還被IEEE科學(xué)與工程計(jì)算期刊列入20世紀(jì)十大算法

庫(kù)利－圖基快速傅里葉變換算法（Cooley-Tukey算法）是最常見(jiàn)的快速傅里葉變換算法。這一方法以分治法為策略遞歸地將長(zhǎng)度為N?=?N1N2的DFT分解為長(zhǎng)度分別為N1和N2的兩個(gè)較短序列的DFT，以及與旋轉(zhuǎn)因子的復(fù)數(shù)乘法。這種方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作發(fā)表An algorithm for the machine calculation of complex Fourier series之后開(kāi)始為人所知。但后來(lái)發(fā)現(xiàn)，實(shí)際上這兩位作者只是重新發(fā)明了高斯在1805年就已經(jīng)提出的算法（此算法在歷史上數(shù)次以各種形式被再次提出）。

庫(kù)利－圖基算法最有名的應(yīng)用，是將序列長(zhǎng)為N的DFT分區(qū)為兩個(gè)長(zhǎng)為N/2的子序列的DFT，因此這一應(yīng)用只適用于序列長(zhǎng)度為2的冪的DFT計(jì)算，即基2-FFT。實(shí)際上，如同高斯和庫(kù)利與圖基都指出的那樣，庫(kù)利－圖基算法也可以用于序列長(zhǎng)度N為任意因數(shù)分解形式的DFT，即混合基FFT，而且還可以應(yīng)用于其他諸如分裂基FFT等變種。盡管庫(kù)利－圖基算法的基本思路是采用遞歸的方法進(jìn)行計(jì)算，大多數(shù)傳統(tǒng)的算法實(shí)現(xiàn)都將顯示的遞歸算法改寫為非遞歸的形式。另外，因?yàn)閹?kù)利－圖基算法是將DFT分解為較小長(zhǎng)度的多個(gè)DFT，因此它可以同任一種其他的DFT算法聯(lián)合使用。

快速傅里葉變換是一個(gè)很有工程價(jià)值的算法，廣泛地應(yīng)用于音頻、圖像等數(shù)字信號(hào)處理軟件中。傅里葉變換本身的理論很深，這里僅以快速多項(xiàng)式乘法為例介紹它在算法競(jìng)賽中的應(yīng)用。快速傅里葉變換（FFT）是用來(lái)計(jì)算離散傅里葉變換（DFT)及其逆變換（IDFT）的快速算法。DFT把時(shí)域信號(hào)變換為頻域信號(hào)。時(shí)域和頻域只是兩種信號(hào)分析的方法，并不是指兩種不同類別的信號(hào)。DFT有一個(gè)很有意思的性質(zhì)：時(shí)域卷積，頻域乘積；頻域卷積，時(shí)域乘積；如果你不知道什么是卷積（convolution),也沒(méi)關(guān)系，請(qǐng)記住：多項(xiàng)式乘法實(shí)際上是多項(xiàng)式系數(shù)向量的卷積。

多項(xiàng)式乘法。給定兩個(gè)單變量多項(xiàng)式A(x),B(x),次數(shù)均不超過(guò)n，如何快速計(jì)算二者的乘積呢？最簡(jiǎn)單的方法就是把系數(shù)兩兩相乘，再相加。這樣計(jì)算的時(shí)間復(fù)雜度是 O（n^2),當(dāng)n很大時(shí)，速度會(huì)很慢。注意，高精度整數(shù)的乘法是多項(xiàng)式乘法的特殊情況，所以多項(xiàng)式乘法的快速乘法也可以用來(lái)做高精度乘法。

上述算法之所以慢是因?yàn)楸硎痉椒ú缓谩ｋm然”系數(shù)序列“是最自然的表示方法，但卻不適合用來(lái)計(jì)算乘法。在多項(xiàng)式快速乘法中，需要用點(diǎn)值法來(lái)表示一個(gè)多項(xiàng)式，點(diǎn)值表示一個(gè)”點(diǎn)—值“對(duì)的序列{(x0,y0),(x1,y1).......(x(n-1),y(n-1))}，它代表一個(gè)多項(xiàng)式，點(diǎn)值法非常適合做乘法：只要兩個(gè)多項(xiàng)式的點(diǎn)集{ xi }相同，則只需要把對(duì)應(yīng)的值乘起來(lái)就可以了，只需要O(n)時(shí)間。但問(wèn)題在于輸入輸出的時(shí)候仍需要采用傳統(tǒng)的系數(shù)表示法，因此需要快速地在系數(shù)表示和點(diǎn)值表示之間轉(zhuǎn)換。還記得上面那句話嗎？時(shí)域卷積，頻域乘積；也就是說(shuō)，多項(xiàng)式的系數(shù)表示法對(duì)應(yīng)于時(shí)域，而點(diǎn)值表示法對(duì)應(yīng)于頻域。因此，只需要用FFT計(jì)算出一個(gè)DFT，就可以完成轉(zhuǎn)換。

單位根。這樣算出來(lái)的點(diǎn)值表示法，對(duì)應(yīng)的求值點(diǎn)是那些？答案是2n次單位根。所謂”n次單位根“，是指滿足x^n=1的復(fù)數(shù)。在復(fù)數(shù)域，1恰好有n個(gè)單位根e^(2k*PI*i / n),其中i是虛數(shù)單位，e^(iu)=cos u+i*sin u.單位根非常特殊，因此FFT才可以在更短時(shí)間內(nèi)求出多項(xiàng)式在這些點(diǎn)的取值。

利用FFT進(jìn)行快速多項(xiàng)式乘法的步驟：

1.補(bǔ)0：在兩個(gè)多項(xiàng)式的最前面補(bǔ)0，得到兩個(gè)2n次多項(xiàng)式，設(shè)系數(shù)向量分別是V1和V2

2.求值：用FFT計(jì)算 f1=DFT(v1)和 f2=DFT(v2).這里的f1和f2分別是兩個(gè)輸入多項(xiàng)式在2n次單位根處的各個(gè)取值（即點(diǎn)值表示）

3.乘法：把兩個(gè)向量f1和f2的每一維對(duì)應(yīng)相乘，得到向量f。它對(duì)應(yīng)多項(xiàng)式乘積的點(diǎn)值表示

4.插值：用FFT計(jì)算v=IDFT(f),其中n就是乘積的系數(shù)向量

多項(xiàng)式求值算法

給定多項(xiàng)式：A(x)=a0+a1*x+a2*x^2+a3*x^3+......+a(n-1)*x^(n-1)

設(shè)x為1的2n次方根，對(duì)所有的x計(jì)算A(x)的值

算法1：對(duì)每個(gè)x做下述運(yùn)算，依次計(jì)算每個(gè)項(xiàng) ai*x^i,(i=0,1,2,3....n-1),然后對(duì) ai*x^i(i=0,1,2,3....n-1)求和

每一項(xiàng)都需要重新計(jì)算，時(shí)間復(fù)雜度是O(n^3)

算法2：依次對(duì)x做下述運(yùn)算，減少不必要的重新計(jì)算，A1(x)=a(n-1),

數(shù)據(jù)結(jié)構(gòu)優(yōu)化

有時(shí)盡管狀態(tài)找好了，轉(zhuǎn)移方程的想好了，但時(shí)間復(fù)雜度比較大，需要用數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。常見(jiàn)的優(yōu)化有二進(jìn)制優(yōu)化、單調(diào)隊(duì)列優(yōu)化、斜率優(yōu)化、四邊形不等式優(yōu)化等。

1、二進(jìn)制優(yōu)化

主要是優(yōu)化背包問(wèn)題，背包九講里面有介紹，比較簡(jiǎn)單，這里只附上幾道題目。

hdu 1059 Diving?

hdu 1171 Big Event in Hdu

poj 1048 Follow My Magic

2、單調(diào)隊(duì)列優(yōu)化

推薦論文：http://wenku.baidu.com/view/4d23b4d128ea81c758f578ae.html

推薦博客：http://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html

hdu 3401 Trade??

poj 3245 Sequece Partitioning?二分+單調(diào)隊(duì)列優(yōu)化

3、斜率優(yōu)化

推薦論文：用單調(diào)性優(yōu)化動(dòng)態(tài)規(guī)劃

推薦博客：http://www.cnblogs.com/ronaflx/archive/2011/02/05/1949278.html

hdu 3507 Print Article

poj 1260 Pearls

hdu 2829 Lawrence

hdu 2993 Max Average Problem

4、四邊形不等式優(yōu)化

推薦博客：http://www.cnblogs.com/ronaflx/archive/2011/03/30/1999764.html

推薦博客：http://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html

hdu 2952 Counting Sheep

poj 1160 Post Office

hdu 3480 Division

hdu 3516 Tree Construction

hdu 2829 Lawrence

四邊形不等式優(yōu)化

今天第一次學(xué)習(xí)四邊形不等式優(yōu)化dp，感覺(jué)優(yōu)化效果十分給力，不過(guò)數(shù)學(xué)味道比較濃重，證明比較復(fù)雜。因此這里刪繁就簡(jiǎn)，給出關(guān)于四邊形不等式優(yōu)化必須要明白的地方，以后直接套用條件即可。

四邊形不等式優(yōu)化條件

1.在動(dòng)態(tài)規(guī)劃中，經(jīng)常遇到如下式的狀態(tài)轉(zhuǎn)移方程：

m(i,j) = min{?m(i,k-1),m(k,j) } + w(i,j)? (i<=k<=j) (min也可以改為max）

m(i,j) 表示在【i，j】區(qū)間上的某個(gè)最優(yōu)值，w(i,j)表示轉(zhuǎn)移時(shí)需要付出的代價(jià)，該方程的時(shí)間復(fù)雜度為O(n^3).

2.下面我們用四邊形不等式來(lái)優(yōu)化上述方程：

（1）區(qū)間包含的單調(diào)性

如果對(duì)于 i <= i' < j <= j'，有w(i' , j) <= w(i , j')?,那么說(shuō)明 W 具有區(qū)間包含的單調(diào)性。

（形象的理解為如果小區(qū)間包含于大區(qū)間，那么小區(qū)間的w值不超過(guò)大區(qū)間的w值）

（2）四邊形不等式

如果對(duì)于 i <= i' < j <= j' ,有 w( i , j ) + w( i' , j' ) <= w ( i , j' )+w( i' , j' )?,我們稱函數(shù)w滿足四邊形不等式

（形象的理解為兩個(gè)交錯(cuò)區(qū)間的和不超過(guò)小區(qū)間與大區(qū)間的和）

兩個(gè)定理：

定理一：如果W函數(shù)同時(shí)滿足區(qū)間包含的單調(diào)性和四邊形不等式，那么函數(shù)m也滿足四邊形不等式

我們?cè)俣xS(i,j)表示m(i,j)取得最優(yōu)值時(shí)對(duì)應(yīng)的下標(biāo)，（即 i<= k <= j 時(shí)，k處的w值最大，則s(i,j)=k )

此時(shí)有如下定理：

定理二：假如 m(i,j)滿足四邊形不等式，那么s(i,j)單調(diào)，即 s(i,j) <= s(i,j+1) <= s(i+1,j+1)

有了上述兩個(gè)定理后，如果w函數(shù)滿足區(qū)間包含單調(diào)性和四邊形不等式性質(zhì)，那么有s(i,j-1) <= s(i,j) <= s(i+1,j)

原來(lái)的狀態(tài)轉(zhuǎn)移方程可以改寫為下式：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)? ?(min也可以改為max）

由于這個(gè)方程枚舉的是區(qū)間長(zhǎng)度L=j-i，而s(i,j-1)和s(i-1,j)的區(qū)間長(zhǎng)度為L(zhǎng)-1，是之前已經(jīng)計(jì)算過(guò)的，可以直接調(diào)用。不僅如此，區(qū)間的長(zhǎng)度最多有n個(gè)，對(duì)于固定的長(zhǎng)度L，不同的狀態(tài)也有n個(gè)，故時(shí)間復(fù)雜度為O(n^2),而原來(lái)的復(fù)雜度為O(n^3),實(shí)現(xiàn)了四邊形不等式的優(yōu)化。今后只需要根據(jù)方程的形式，以及w函數(shù)是否滿足上述兩條性質(zhì)，即可考慮使用四邊形不等式來(lái)優(yōu)化。

?

總結(jié)

以上是生活随笔為你收集整理的dp进阶之FFT加速+数据结构优化+不等式优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。