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

  • Uploaded by: Abel ORian
  • 0
  • 0
  • April 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Análisis De Eficiencia De Algoritmos Para Calcular Dft Y Fft as PDF for free.

More details

  • Words: 435
  • Pages: 7
“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.

Related Documents


More Documents from ""

April 2020 2
Analisis De Grafos
May 2020 10
Fibonacci Heap
May 2020 5
Document
August 2019 47
December 2019 34