Es posible hacer un algoritmo más rápido que la transformada rápida de Fourier para calcular la transformada de Fourier discreta (hay pruebas a favor o en contra)?
O, una que sólo se aproxima a la transformada de Fourier discreta, pero es más rápido que el $O(NlogN)$ y todavía da unos resultados razonables?
Requisitos adicionales:
1) Vamos a dejar la computación cuántica fuera
2) no quiero decir más rápido en el sentido de cómo su implementado por algún hardware específico, pero en el "Big-O notación de sentido", que se corrió por ejemplo, en el tiempo lineal.
Lo siento por mi inglés
