Análisis De Eficiencia De Algoritmos Para Calcular Dft Y Fft

“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.