Aufwand bei der FFT < Fourier-Transformati < Transformationen < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegen sei [mm] \omega_N=e^{-2\pi*i/N} [/mm] mit [mm] N=2^n. [/mm] Dann ist es möglich den Fourier Koeffizienten einer Funktion auf [mm] \IZ(N) [/mm] mit maximal
[mm] 4*2^n*n [/mm] = [mm] 4*N*log_2(N)=O(N*logN) [/mm]
Operationen zu berechnen. |
Guten Abend,
ich bereite mich gerade für ein Seminar zur Fourier Analysis auf einen Vortrag über die Schnelle Fourier Transformation vor. In der Literatur, die der Dozent mir gegeben hat, steht der oben genannte Satz. Ich habe versucht den Ausdruck nachzuvollziehen, habe auch verstanden, was [mm] 2^n*n [/mm] bzw. [mm] N*log_2(N) [/mm] bedeuten, aber ich kann mir nicht erklären, was die 4 zu bedeuten hat.
Wenn jemand eine Erklärung parat hat oder mir einen hilfreichen Tipp geben kann, wäre ich sehr dankbar.
Wahrscheinlich sehe ich den Wald vor lauter Bäumen einfach nicht.
Vielen Dank schon mal im Voraus :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:18 Mo 03.07.2017 | | Autor: | leduart |
Hallo
den Faktor 4 kann man wohl nur erklären , wenn man den Beweis der Aussage kennt.
aber warum sollte er nicht da stehen?
Gruß leduart
|
|
|
|
