Transformada ràpida de Fourier: diferència entre les revisions

L'avaluació directa d'aquesta fórmula requereix O(''n''²) operacions aritmètiques. Mitjançant un algoritmealgorisme FFT es pot obtenir el mateix resultat amb tan sols O(''n'' log ''n'') operacions. En general, aquests algoritmesalgorismes depenen de la factorització de ''n'' però, al contrari del que freqüentment es creu, existeixen FFTs per a qualsevol ''n'', inclús amb ''n'' primer.

Una ''O''(''N''^5/2 log ''N'') la generalització d'harmònics esfèrics en l'esfera ''S''² amb ganglis ''N''² va ser descrit per Mohlenkamp (1999), juntament amb un algoritmealgorisme de conjectura (però no està provat) que ''O''(''N''² log² ''N' la complexitat; Mohlenkamp també proporciona una implementació de la biblioteca libftsh. Un algorisme d'harmònics esfèrics, amb 'O''(''N''² log ''N'') la complexitat és descrita per Rokhlin i Tygert (2006).

Diversos grups han publicat també "FFT" algorismes per a les dades no equiespaiats, tal com va ser revisat en Potts et al. (2001). Aquests algoritmesalgorismes de no ser estrictament calcular la DFT (que només està definit per a les dades equiespaiats), sinó més aviat una aproximació dels mateixos (un no-uniforme de Fourier discret transforma, o NDFT, que és sovint només es calcula aproximadament).