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