Interpretación geométrica Definido el producto escalar entre funciones de la siguiente manera: la transformada de Fourier se puede entender como el producto escalar entre la función x(t) y la exponencial compleja evaluado sobre todo el rango de frecuencias f. Por la interpretación usual del producto escalar, en aquellas frecuencias en las que la transformada tiene un valor mayor, más parecido tiene x(t) con una exponencial compleja. EJEMPLO:
N 10 100 1000 106 109 N2 100 104 106 1012 1018 NlogN 1 200 3000 6×106 9×109 En la figura muestra que tan lento crece el tiempo de solución de un proceso de O(NlogN). Digamos que tiene una maquina de 1 MFLOP (un millión de "puntos flotantes" de operacione spor segundo). Sea N=1millión=106. Un algoritmo de O( N2) toma 1012 procesos → 106 segundos ≃ 11.5 días. Un algoritmo de O( NlogN) toma 6×106 procesos → 6 segundos. nota: N=1millión es razonable. Ejemplo 1 Una camara digital de 3 megapixeles arroja 3×106 números por cada foto. Así que para dos N secuencias de punto f[n] y h[n] . Si resolvemos directamente (f[n] ,⊛,h[n] ) : O( N2) operaciones. Tomando la FFTs -- O(NlogN) multiplicando la FFTs -- O(N) la inversa de FFTs -- O(NlogN). el total de complejidad es O(NlogN). nota: FFT + computación didigital fue completamente responsable de la "explosión" del Procesamiento Digital de Señales DSP en los años 60's.