כל מה שרצית לדעת על FFT:
התמרת פורייה מהירה (באנגלית Fast Fourier Transform (FFT)) היא אלגוריתם יעיל לחישוב התמרת פורייה בדידה ((Discrete Fourier Transform (DFT) וההתמרה ההופכית שלה.
יש מספר רב של אלגוריתמי FFT הכוללים טווח רחב של ענפים במתמטיקה מאריתמטיקה של מספרים מרוכבים לתורת החבורות ותורת המספרים.
ערך זה סוקר את הטכניקות וחלק מתכונותיהן הכלליות.
DFT ממיר סדרה של ערכים לרכיבים של תדירויות שונות.
פעולה זו שימושית בתחומים רבים, אך חישוב ישיר של ההתמרה לפי ההגדרה שלה הוא פעמים רבות איטי מכדי להיות פרקטי.
FFT היא שיטה לחשב את אותה תוצאה באופן מהיר יותר.
חישוב DFT של N נקודות באופן נאיבי על פי ההגדרה הינו בעל סיבוכיות של , בעוד ש-FFT הינו בעל סיבוכיות של .
ההבדל במהירות עשוי להיות משמעותי, במיוחד עבור סדרות ארוכות בהן עשוי להיות סדר גודל של אלפים או מיליונים.
זמן החישוב יכול להיות מופחת בכמה סדרי גודל במקרים אלו, והשיפור הוא פרופורציונלי ל-.
שיפור עצום זה הפך אלגוריתמים רבים מבוססי DFT להיות פרקטיים.
FFT הם בעלי חשיבות רבה למגוון רחב של אפליקציות החל מעיבוד אותות ספרתי ופתרון משוואות דיפרנציאליות חלקיות לאלגורתמים למכפלה מהירה של מספרים טבעיים גדולים.
אלגורתמי FFT הידועים ביותר מבוססים על פקטוריזציה של , אך ישנם אלגוריתמי FFT בעלי סיבוכיות של לכל , אפילו עבור ראשוני.