第五百八十六章 快速傅里葉變換（傅立葉分析）

　　傅里葉分析革命了數(shù)學(xué)哲學(xué)，但是卻留下一個大麻煩，就是計(jì)算量太大。后人對此做的努力都是在想方設(shè)法的減小計(jì)算量，也能得到時域和頻域的轉(zhuǎn)換結(jié)果。

　　離散傅里葉變換（DFT），是傅里葉變換在時域和頻域上都呈現(xiàn)離散的形式，將時域信號的采樣變換為在離散時間傅里葉變換（DTFT）頻域的采樣。

　　美國數(shù)學(xué)家?guī)炖锖蛨D基發(fā)明快速傅里葉變換，把時間復(fù)雜度降低一個量級。

　　dft是離散傅里葉變換，fft是快速離散傅里葉變換，讓離散傅里葉變換所需要乘法次數(shù)減少，被變換的抽樣點(diǎn)越多，fft算法越顯著。

　　快速傅氏變換（FFT），是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實(shí)等特性，對離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。

　　不是新發(fā)現(xiàn)，但在計(jì)算機(jī)中變得方便。

　　把此公示寫出來，弄成離散的，再表示成矩陣的。

　　利用對稱性，先減少一半的計(jì)算量。

　　然后把一分為二的思想進(jìn)行下去，達(dá)到極致，機(jī)會極大的減少計(jì)算量。

　　所以點(diǎn)數(shù)越多，優(yōu)勢越明顯。