A definíció szerinti megfogalmazásban a diszkrét Fourier-transzformáció időbonyolultsága . Az időbonyolultság az algoritmuselmélet területén az algoritmusok számításigényének jellemzésére kidolgozott mérőszám, melyet esetünkben úgy értelmezhetünk, hogy a diszkrét Fourier-transzformáció algoritmusa N hosszúságú bemenet esetén nagyságrendileg lépést hajt végre az eredmény meghatározásához.

A gyors Fourier-transzformáció (Fast Fourier Transform – FFT) valójában nem egyetlen módszer, hanem inkább egy algoritmuscsalád, amely N hosszúságú bemenet diszkrét Fourier-transzformáltját -nel arányos lépésben számítja ki. A művelet miatt az FFT jóval hatékonyabb, mint a klasszikus, definíció szerinti DFT, mégis ugyanarra az eredményre vezet. Könnyen látható, hogy egy kicsinek tekinthető, 128 elemű vektor diszkrét Fourier-transzformációjának definíció szerinti kiszámításához nagyságrendileg 16384 számítási műveletet kell végrehajtani, míg egy időbonyolultságú algoritmus esetén csak 1024-et. Az FFT bevezetése J. W. Cooley és J. Tukey nevéhez fűződik, akik az IBM alkalmazásában dolgozták ki az első FFT algoritmust 1965-ben. Az 1994-ben megjelent, Linear Algebra and Its Applications című klasszikus matematikai művében Gilbert Strang „napjaink legfontosabb numerikus algoritmusa”-ként hivatkozik rá, mely „milliárdszor fut nap mint nap”. Természetesen azóta ez a szám ezermilliárdokra tehető.

A számos gyors Fourier-transzformáció variáns közül a klasszikus Cooley–Tukey algoritmust vezetjük le és mutatjuk be a szakasz hátralévő részében. Az FFT módszerek közös tulajdonsága, hogy egyaránt az oszd meg és uralkodj elv alapján, rekurzívan működnek. A Cooley–Tukey algoritmus méretű vektorok transzformáltjának kiszámítására ad megoldást, de mint látni fogjuk, a gyakorlati alkalmazások szempontjából ez egyáltalán nem jelent megszorítást.

Az egyszerűbb leírás kedvéért vezessünk be néhány új jelölést. Legyen , , és jelölje az N elemű vektorok diszkrét Fourier-transzformáltját kiszámító függvényt. Jelölje az x páros, a páratlan koordinátájú elemeinek diszkrét Fourier-transzformáltját, azaz

Az algoritmus fő gondolata az, hogy a DFT-t előbb a vektor páros, majd páratlan indexű elemeire alkalmazzuk és az így kapott, hosszúságú vektorokból kombináljuk ki az eredményt. Amint az az alábbi levezetésből látható, mindez tényleg megvalósítható.

A definíció szerinti diszkrét Fourier-transzformáció felbontható két részösszeg összegére az alábbi módon

A második összegzés exponenciális tagjában van egy összeadás, így felbontva az exponenciális kifejezést, kiemelhetjük a szumma kvantor által kötött n indexet nem tartalmazó tényezőt:

Az egyenlőség jobb oldalának két összegzése az eredeti x vektor páros és páratlan indexű elemeiből álló hosszúságú vektorok DFT-jének a k indexű elemeit adja, azaz

Azonban, az x vektor páros indexű elemeinek DFT-jére és páratlan indexű elemeinek DFT-jére újra alkalmazhatjuk a fenti dekompozíciót, így rekurzívan eljuthatunk a 2 elemű vektorok DFT-jéig. Kettő elemű vektorok diszkrét Fourier-transzformációja pedig

így nagyon gyorsan kiszámítható.

A fenti levezetés egyetlen szépséghibája, hogy miután felbontottuk az N hosszúságú vektor DFT-jét két hosszúságú vektor DFT-jére, azokkal csak a indexű elemeket számítjuk ki direkt módon. Ennek megfelelően némi kiegészítést kell tennünk, hogy a kettő elemű vektorok Fourier-transzformáltjaiból valóban visszakapjuk az eredeti, N elemű vektor transzformáltját. Kihasználva a DFT periodicitásáról szóló tétel állítását, könnyen látható, hogy és . Lássuk, hogyan alakul a páratlan részből kiemelt szorzó tényező, ha azt a helyen értékeljük ki:

ahol az utolsó lépésben kihasználtuk, hogy , azaz a kiemelt szorzó faktor előjelet vált. Ezek alapján a diszkrét Fourier-transzformáció gyors, rekurzív kiszámítására az alábbi formulát kapjuk:

Az inverz gyors Fourier-transzformációt analóg módon levezetve az alábbi formális kifejezéshez jutunk:

A gyors Fourier-transzformáció és inverz gyors Fourier-transzformáció közötti különbség egyedül a komplex hullámok kitevőjében jelentkezik.

A Cooley–Tukey-féle gyors Fourier-transzformáció méretű vektorokra van kidolgozva. Felmerülhet az olvasóban a kérdés, hogy mi a teendő, ha a vektorunk nem hosszúságú? A válaszokat az alábbiakban foglaljuk össze.