Fast Fourier Transform เป็น algorithm การทำ Discrete Fourier Transform ที่ complexity ลดลงครับ
ผมจำไม่ได้ว่าลดจากเท่าไรเป็นเท่าไร (คิดว่าจาก O(n^2) เป็น O(nlogn))
โดยผลลัพธ์การทำ FFT ที่ได้จะตรงกับการทำ DFT ทุกประการนะครับ เพียงแต่เร็วกว่า (ในแง่ของ complexity)
โดย FFT ก็ไม่ได้หมายถึง algorithm ใด algorithm หนึ่งเฉพาะเจาะจงนะครับ มีคนเสนอมาหลายแบบ แต่ก็จะมีแบบหนึ่งที่นิยมใช้กัน (ผมจำไม่ได้อีกแล้วว่าของใคร ขอโทษด้วยครับ)
อย่างไรก็ตาม ก็ยังมี FFT แบบที่ให้คำตอบไม่ตรงเป๊ะด้วยนะ แลกกันกับความเร็วครับ