“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 Jeltsch Marzo 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 T(1) = C
n>1
Usando el Teorema Maestro: T(n) = a T(n/b) + f(n), donde: a=2 b=2 f(n) = n/2 F(n) = ½ n = ½ n^log 2 (2) = ½ n n/2 Є Θ (n) T(n) Є Θ (n*log n)
Pruebas de FFT y DFT N 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192
FFT (n log n) 2 8 24 64 160 384 896 2048 4608 10240 22528 49152 106496
DFT (n*n) 4 16 64 256 1024 4096 16384 65536 262144 1048576 4194304 16777216 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. N 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192
FFT DFT (microSeg) (microSeg) 5 9 8 13 12 30 20 109 39 417 85 1651 185 6689 407 26929 917 106712 2966 444358 6648 1781026 13405 7167926 32610 30037472
Tabla 2: Valores extraídos de la ejecución de ambos algoritmos.
Tiempo (microSeg)
Costos 1000000 900000 800000 700000 600000 500000 400000 300000 200000 100000 0 0
1000
2000
3000
4000
5000
6000
7000
8000
9000
N 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.