Resolución Ejercicio 3 - Benchmark y Análisis de Complejidad de la DFT

Planteo del Benchmark

El objetivo es empíricamente evaluar el rendimiento de nuestra implementación de la DFT (calcular_dft()) frente al aumento del tamaño de entrada $N$. El enunciado nos pide variar la frecuencia de sampleo $f_s \in \{10, 100, 1000, 10000\}$ Hz. Como mantenemos la duración de la señal en $T = 2\text{ s}$, la cantidad total de muestras $N = f_s \cdot T$ escala directamente con la frecuencia de sampleo.

Complejidad Computacional (Big $\mathcal{O}$)

Nuestra implementación es matricial:

$$X = M \cdot x$$

Donde $M$ es una matriz de $N \times N$ elementos, y $x$ un vector columna de $N$ elementos. Analicemos dos tipos de complejidad:

1. Complejidad Temporal: Para multiplicar una matriz de $N \times N$ por un vector $N \times 1$, se requieren del orden de $N^2$ operaciones elementales (sumas y multiplicaciones complejas). Por tanto, la complejidad temporal es $\mathcal{O}(N^2)$.
2. Complejidad Espacial: Para generar la matriz de pesos $M$, necesitamos alojar en memoria RAM $N \times N$ números complejos de punto flotante de doble precisión (complex128, 16 bytes cada uno). Por tanto, la complejidad espacial también es $\mathcal{O}(N^2)$.

El colapso del Hardware

Al ejecutar el script de testeo (ejercicio3.py), presenciamos un evento pedagógico brutal: un colapso directo por límite físico (MemoryError).

$f_s$ (Hz)	Longitud $N$	Tiempo (s)	Memoria Teórica Requerida
10	20	$\approx$ 0.0001	6.4 KB
100	200	$\approx$ 0.003	640 KB
1000	2000	$\approx$ 0.28	64 MB
10000	20000	FALLA	$\approx$ 6 GB contiguos

Cuando $N = 20000$, la matriz de pesos $M$ necesita alojar $20000 \times 20000 = 400.000.000$ números complejos. Al pesar 16 bytes cada uno, Numpy le solicita al SO un bloque contiguo de $\sim 6$ GiB. En una PC de escritorio estándar ejecutando Python en Windows, este intento de asignación contigua falla estrepitosamente arrojando Unable to allocate 5.96 GiB.

Modificamos el script para capturar el MemoryError y continuar graficando los puntos que sí tuvieron éxito.

Análisis Gráfico Log-Log

Para visualizar relaciones de la forma $T(N) = c \cdot N^\alpha$, la técnica estándar es aplicar el logaritmo a ambos lados:

$$\log(T) = \alpha \log(N) + \log(c)$$

Esto significa que, graficado en ejes Log-Log, deberíamos ver una recta cuya pendiente es precisamente el exponente $\alpha$. Al ajustar linealmente nuestros puntos exitosos (ignorando el primero por ser demasiado rápido y estar dominado por el overhead de Python), el script arrojó una pendiente de $\approx 2$. Esto prueba empíricamente nuestro análisis teórico: la implementación matricial escala cuadráticamente con el tamaño del problema.

[!infobox] Ejercicio 3: Rendimiento de la DFT matricial Contexto: Análisis de complejidad temporal y espacial empírica. Resolución Analítica/Numérica: Se midieron los tiempos de ejecución mediante time.perf_counter(). Se trazó un gráfico Log-Log estimando la pendiente mediante regresión lineal (np.polyfit), confirmando empíricamente que el tiempo crece como $\mathcal{O}(N^2)$. Advertencia/Clave: La implementación naive matricial colapsó por memoria (MemoryError) al llegar a $N=20000$ debido a su crecimiento espacial $\mathcal{O}(N^2)$ (casi 6GB de RAM requeridos). Este fracaso absoluto demuestra por qué en el mundo real NADIE usa la definición cruda de la Transformada Discreta; se utiliza exclusivamente la FFT (Fast Fourier Transform), que reduce la complejidad temporal a $\mathcal{O}(N \log N)$ y elimina la matriz gigante reduciendo la espacial a $\mathcal{O}(N)$.