Zahl der Operationen beim FFT-Verfahren
- Ist N eine Zweierpotenz ist, so beträgt die Zahl der Operationen
(Multiplikationen und Additionen) beim FFT-Verfahren
- Beweis:
- Aus der Aufspaltung der Fourierreihe in je eine Fourierreihe
für gerade und ungerade Indizes ergab sich die Rekursionsbeziehung
- Induktionsanfang:
- Für N = 1 ist die Fourierreihe einfach
- also gilt
- Induktionsschritt:
- Mit der Rekursionsformel und der Induktionsvoraussetzung
erhält man durch einfache Rechnung