<< Chapter < Page | Chapter >> Page > |
La Transformada Rápida de Fourier (Fast Fourier Transform) (FFT) es un algoritmo eficiente O(NlogN) para calcular la DFT
¿En cuánto es mejor O(NlogN) que O( $N^{2}$ )?
$N$ | $10$ | $100$ | $1000$ | $10^{6}$ | $10^{9}$ |
---|---|---|---|---|---|
$N^{2}$ | 100 | $10^{4}$ | $10^{6}$ | $10^{12}$ | $10^{18}$ |
$N\lg N$ | $1$ | $200$ | $3000$ | $610^{6}$ | $910^{9}$ |
Digamos que tiene una maquina de 1 MFLOP (un millión de "puntos flotantes" de operacione spor segundo). Sea $N=1\mathrm{milli\xf3n}=10^{6}$ .
Un algoritmo de O( $N^{2}$ ) toma $10^{12}$ procesos→ $10^{6}$ segundos≃11.5 días.
Un algoritmo de O( $N\lg N$ ) toma $610^{6}$ procesos→6 segundos.
Una camara digital de 3 megapixeles arroja $310^{6}$ números por cada foto. Asíque para dos $N$ secuencias de punto $f(n)$ y $h(n)$ . Si resolvemos directamente $\u229b(f(n), h(n))$ : O( $N^{2}$ ) operaciones.
Tomando la FFTs -- O(NlogN)
multiplicando la FFTs -- O(N)
la inversa de FFTs -- O(NlogN).
el total de complejidad es O(NlogN).
Notification Switch
Would you like to follow the 'Señales y sistemas' conversation and receive update notifications?