“Análisis de eficiencia de algoritmos para calcular DFT y FFT”
Nombre: Abel O’Rian A.Asignatura: Diseño y Análisis de Algoritmos
Profesor: Eric JeltschMarzo 2009
“Yo Abel O’Rian A., certifico que este trabajo es el resultado de mi propio esfuerzo. Además, el material de apoyo, fuente de información o colaboración utilizados han sido citado y agradecido. Finalmente, estoy conciente de la falta a la ética que representa el engañar a mi profesor y a mis compañeros de curso, si es que se constata, aunque la Universidad no tenga medidas disciplinarias al respecto.
Análisis DFT:
Revisando el código de este algoritmo se ve claramente su funcionamiento.Al inicio se generan un conjunto de números al azar. Luego se calcula N*N veces lo siguiente:
El N*N veces que se calcula esto, se ve en 2 for, uno anidado en otro. Esto da un costo de complejidad de O(N^2).
Análisis FFT:
El algoritmo de FFT calcula el DFT usando el método de “Divide Y Vencerás”. EN el código se puede ver las 2 llamadas recursivas a FFT de tamaño N/2, más el N/2 operaciones para combinar los subproblemas.
T(n) = 2 T(n/2) + N/2 n>1T(1) = C
Usando el Teorema Maestro:
T(n) = a T(n/b) + f(n), donde: a=2b=2f(n) = n/2
F(n) = ½ n = ½ n^log 2 (2) = ½ n
n/2 Є Θ (n) T(n) Є Θ (n*log n)
Pruebas de FFT y DFT
NFFT
(n log n)DFT
(n*n)2 2 44 8 168 24 64
16 64 25632 160 102464 384 4096
128 896 16384256 2048 65536512 4608 2621441024 10240 10485762048 22528 41943044096 49152 167772168192 106496 67108864
Tabla 2: Comparación entre el número de operaciones en el cálculo de DFT y FFT.
Figura : Ejecución de programa con GUI
Figura: Programa desde consola.
NFFT (microSeg)
DFT (microSeg)
2 5 94 8 138 12 30
16 20 10932 39 41764 85 1651
128 185 6689256 407 26929512 917 106712
1024 2966 4443582048 6648 17810264096 13405 71679268192 32610 30037472
Tabla 2: Valores extraídos de la ejecución de ambos algoritmos.
Costos
0
100000
200000300000
400000
500000
600000
700000800000
900000
1000000
0 1000 2000 3000 4000 5000 6000 7000 8000 9000
N
Tie
mp
o (
mic
roS
eg
)
FFT DFT
Figura 2: Grafico de costos de ejecución (tiempo)
Se ve claramente que el costo de ejecución baja considerablemente con el algoritmo de FFT, que tiene un costo Θ (n log n). , con lo que la teoría se demuestra al ejecutar el
programa.