Schnelle Fourier-Transformation (FFT)

Eine Algorithmusfamilie, die die diskrete Fourier-Transformation (DFT) einer Folge effizient berechnet, indem Symmetrien, Periodizitäten und rekursive Faktorisierung der DFT-Matrix ausgenutzt werden, wodurch die Rechenkomplexität in typischen Fällen von O(N^2) auf O(N log N) sinkt.