FFTKomplexität

FFT-Komplexität bezeichnet den Rechenaufwand, der bei der schnellen Fourier-Transformation (FFT) zur Berechnung der diskreten Fourier-Transformation (DFT) angegeben wird. Im Gegensatz zur direkten DFT, die O(N^2) Operationen erfordert, liegt die asymptotische Komplexität einer FFT bei O(N log N) für N-Punkt-Transformationen. Diese Komplexität gilt unabhängig davon, ob Vor- oder Rückwärts-Transformationsrechnungen betrachtet werden, wobei die konkrete Anzahl der Operationen durch Implementierung und Datentyp beeinflusst wird.

Bei einem typischen Fall, dem radix-2 FFT, der für N gleich einer Potenz von zwei implementiert wird, ergibt sich eine grobe Obergrenze von etwa (N/2) log2 N komplexen Multiplikationen und N log2 N komplexen Additionen. Real-Werteingänge ermöglichen oft weitere Optimierungen, sodass sich der Rechenaufwand im Durchschnitt reduziert. Für Realdaten lassen sich durch Symmetrieeigenschaften oft die Hälfte der Rechenoperationen einsparen.

Nicht-potenzielle Längen oder spezifische Anforderungen erfordern andere Ansätze. Mixed-Radix-FFT-Algorithmen erreichen weiterhin O(N log N) Komplexität. Für manche Größen stellen Bluestein- oder Rader-Algorithmen Umwandlungen auf Faltungsprobleme dar, die wiederum mittels FFT gelöst werden; dadurch verschiebt sich die Grundkomplexität auf größere FFT-Größen.

Speicherbedarf und Praktikabilität: In-place-Implementierungen benötigen typischerweise O(N) Speicher, zusätzlich können Puffer für bestimmte Optimierungen verwendet werden. Die effektive Leistung hängt stark von Hardware, Speicherbandbreite, Cacheverhalten, Vectorisierung und Parallelisierung ab. Real- oder komplexe Datenformate und Padding beeinflussen ebenfalls die praktischen Konstanten hinter der O(N log N)-Skalierung.