第五百八十六章 快速傅裏葉變換(傅立葉分析)

    傅裏葉分析革命了數學哲學，但是卻留下一個大麻煩，就是計算量太大。後人對此做的努力都是在想方設法的減小計算量，也能得到時域和頻域的轉換結果。


    離散傅裏葉變換（dft），是傅裏葉變換在時域和頻域上都呈現離散的形式，將時域信號的采樣變換為在離散時間傅裏葉變換（dtft）頻域的采樣。


    美國數學家庫裏和圖基發明快速傅裏葉變換，把時間複雜度降低一個量級。


    dft是離散傅裏葉變換，fft是快速離散傅裏葉變換，讓離散傅裏葉變換所需要乘法次數減少，被變換的抽樣點越多，fft算法越顯著。


    快速傅氏變換（fft），是離散傅氏變換的快速算法，它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。


    不是新發現，但在計算機中變得方便。


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


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


    然後把一分為二的思想進行下去，達到極致，機會極大的減少計算量。


    所以點數越多，優勢越明顯。