title: "1A. Reporte escrito. Experimentos y análisis." subtitle: "Análisis de Algoritmos 2025-2" author: "Mendiola Alavéz Dalia Isabel" format: pdf: documentclass: article fontsize: 11pt geometry: margin=1in code-overflow: wrap output-width: 0.9\textwidth include-in-header: text: | \usepackage{fancyhdr} \pagestyle{fancy} \fancyhead[L]{Mendiola Alavéz Dalia Isabel} \fancyhead[R]{Materia: Análisis de Algoritmos 2025-2} \fancyfoot[C]{\thepage} \usepackage[htt]{hyphenat}
Introducción
El diseño y análisis de algoritmos constituye un pilar fundamental en la ciencia de la computación, ya que permite resolver problemas de manera eficiente mediante una secuencia finita y ordenada de pasos denominada algoritmo. La elección de una estructura de datos adecuada, entendida como la forma en que se organiza y almacena la información para su posterior manipulación, es determinante para el rendimiento de dicho algoritmo (Cormen et. al., 2022).
El estudio de los algoritmos se apoya en modelos de cómputo, los cuales son representaciones teóricas del funcionamiento de un procesador. Entre estos, el modelo RAM (Random Access Machine) es el más utilizado en el análisis, dado que asume tiempos constantes para operaciones básicas y acceso directo a memoria (Aho et.al., 1983).
La evaluación del rendimiento se realiza mediante tipos de análisis que consideran el mejor caso, el peor caso y el caso promedio, dependiendo de las condiciones de entrada. Para expresar dicho rendimiento, se recurre a la notación asintótica, una herramienta matemática que describe el comportamiento del algoritmo a medida que el tamaño de la entrada crece, ignorando constantes y términos de menor grado (Knuth, 1976).
Finalmente, el rendimiento de un algoritmo se clasifica en órdenes de crecimiento, que representan la velocidad con que aumentan los recursos requeridos —como tiempo o memoria— en función del tamaño de los datos procesados. Entre ellos se encuentran órdenes como $O(1)$, $O(log n)$, $O(n)$, $O(n log n)$ y $O(n^{2})$, cada uno con implicaciones directas en la escalabilidad y eficiencia de las soluciones computacionales (Sedgewick et. al., 2011).
En conjunto, estos conceptos ofrecen el marco teórico necesario para comparar, seleccionar y optimizar algoritmos, contribuyendo a un desarrollo de software más robusto y eficiente.
En este trabajo se evalúan diversos órdenes de crecimiento y se discuten las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información, utilizando Python como lenguaje de programación.
# Comenzamos importando las librerías a utilizar:
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import math
from math import log10, e, pi, factorial
1. Definición de las funciones a evaluar
# Complejidad constante O(1)
def O1(n):
return np.ones_like(n)
# Complejidad logarítmica O(log n)
def Ologn(n):
return np.log(n)
# Complejidad lineal O(n)
def On(n):
return n
# Complejidad casi lineal O(n log n)
def Onlogn(n):
return n * np.log(n)
# Complejidad cuadrática O(n^2)
def On2(n):
return n**2
# Complejidad cúbica O(n^3)
def On3(n):
return n**3
# Complejidad exponencial O(a^n)
def Oa_power_n(n, a=2):
return a**n
# Complejidad factorial O(n!)
def On_factorial(n):
from math import factorial
return np.array([factorial(int(i)) for i in n], dtype=float)
# Complejidad super-exponencial O(n^n)
def On_power_n(n):
return n**n
# Complejidad exponencial específica O(2^n)
def O2n(n):
return 2**n
# Complejidad raíz cuadrada O(sqrt(n))
def On_sqrt(n):
return np.sqrt(n)
2. Establecimiento de los rangos adecuados para cada comparación.
# Comparación 1: O(1) vs O(log n)
# - Escala biológica: número de células analizadas
n_range_1 = np.linspace(1, 1000, 1000)
# Comparación 2: O(n) vs O(n log n)
# - Escala física: conteo de partículas microscópicas
n_range_2 = np.linspace(1, 1000, 1000)
# Comparación 3: O(n^2) vs O(n^3)
# - Escala computacional: simulaciones de interacciones moleculares
n_range_3 = np.linspace(1, 100, 100)
# Comparación 4: O(a^n) vs O(n!)
# - Escala biológica: combinaciones genéticas (a=2 para mutaciones binarias)
n_range_4 = np.arange(1, 15)
# Comparación 5: O(n!) vs O(n^n)
# - Escala astronómica: combinaciones de estados cuánticos
n_range_5 = np.arange(1, 8)
3. Creación de las figuras de comparación (Se incluye el paso 4. 'Discute lo observado por figura')
- $\mathbf{O(1) \ \text{vs} \ O(\log n)}$
# Comparación 1
plt.figure(figsize=(8,5))
plt.plot(n_range_1, O1(n_range_1), label="O(1)", linewidth=2, color ='royalblue')
plt.plot(n_range_1, Ologn(n_range_1), label="O(log n)", linewidth=2, color ='blueviolet')
plt.xlabel("n (ej. número de células analizadas)")
plt.ylabel("Tiempo relativo")
plt.title("O(1) vs O(log n)", fontsize=12, fontweight='bold')
plt.legend()
plt.grid(True)
plt.show()
Discusión
En el análisis de la eficiencia algorítmica, se observa que los algoritmos con complejidad $O(1)$ permanecen constantes sin importar el tamaño de los datos, lo que los convierte en una opción ideal para operaciones que deben ejecutarse de manera uniforme en distintos contextos. Por su parte, los algoritmos con complejidad $O(\log n)$ crecen muy lentamente, lo que los hace altamente eficientes incluso para valores grandes de $n$. Un ejemplo ilustrativo en contextos biológicos es considerar $n$ como el número de células en una muestra, donde $n \approx 10^{6}$; en este caso, $log_{2}(n)\approx 20$, lo que implica que el incremento en el costo computacional es mínimo en comparación con el tamaño de los datos. Esto demuestra que tanto $O(1)$ como $O(\log n)$ constituyen clases de algoritmos particularmente ventajosas para el análisis de información masiva, ya que permiten escalar a volúmenes grandes de datos con un impacto reducido en los tiempos de ejecución (Cormen et al., 2022).
- $\mathbf{O(n) \ \text{vs} \ O(n \log n)}$
# Comparación 2
plt.figure(figsize=(8,5))
plt.plot(n_range_2, On(n_range_2), label="O(n)", linewidth=2, color ='royalblue')
plt.plot(n_range_2, Onlogn(n_range_2), label="O(n log n)", linewidth=2, color ='blueviolet')
plt.xlabel("n (ej. partículas en una muestra)")
plt.ylabel("Tiempo relativo")
plt.title("O(n) vs O(n log n)", fontsize=12, fontweight='bold')
plt.legend()
plt.grid(True)
plt.show()
Discusión
En términos de eficiencia, los algoritmos con complejidad $O(n)$ crecen de manera estrictamente lineal con respecto al tamaño de los datos, lo que los hace mucho más costosos que algoritmos logarítmicos a medida que $n$ aumenta. Por ejemplo, si se considera $n = 10^{6}$, se tiene que $log_2(n) \approx 20$, mientras que $O(n) = 10^{6}$, lo que evidencia la diferencia sustancial en el número de operaciones requeridas. De manera similar, los algoritmos con complejidad $O(n \log n)$ también presentan un crecimiento lineal, pero con un factor adicional de complejidad logarítmica, lo que los hace más demandantes que $O(n)$, aunque todavía manejables en comparación con algoritmos de orden superior. En un contexto físico, este tipo de comportamiento puede ilustrarse al ordenar partículas detectadas en un experimento, donde el costo computacional escala con el número de elementos procesados. Estos ejemplos reflejan cómo la selección del algoritmo adecuado depende no solo del tamaño de los datos, sino también de la tolerancia al costo de cómputo en situaciones de gran escala (Cormen et. al., 2022).
- $\mathbf{O(n^2) \ \text{vs} \ O(n^3)}$
# Comparación 3
plt.figure(figsize=(8,5))
plt.plot(n_range_3, On2(n_range_3), label="O(n^2)", linewidth=2, color ='royalblue')
plt.plot(n_range_3, On3(n_range_3), label="O(n^3)", linewidth=2, color ='blueviolet')
plt.xlabel("n (ej. moléculas en simulación)")
plt.ylabel("Tiempo relativo")
plt.title("O(n²) vs O(n³)", fontsize=12, fontweight='bold')
plt.legend()
plt.grid(True)
plt.show()
Discusión
En el análisis comparativo de la complejidad algorítmica, se observa que $O(n^3)$ crece considerablemente más rápido que $O(n^2)$, lo que implica un incremento drástico en el tiempo de cómputo conforme aumenta el tamaño de entrada. En biología computacional, este comportamiento puede asociarse al modelado de interacciones moleculares, donde pasar de pares de moléculas $O(n^2)$ a tríos $O(n^3)$ eleva notablemente la complejidad del problema. Por otro lado, los algoritmos con complejidad $O(n \log n)$ crecen más rápido que los lineales $O(n)$, pero siguen siendo manejables en la práctica. Este tipo de complejidad es característico de algoritmos de ordenamiento eficientes, como Merge Sort o Heap Sort, ampliamente utilizados debido a su buen balance entre eficiencia y escalabilidad. En conjunto, estas comparaciones evidencian que la complejidad polinómica y casi lineal determinan la viabilidad de resolver problemas reales en función del tamaño de los datos y los recursos computacionales disponibles (Cormen et. al., 2022).
- $\mathbf{O(a^n) \ \text{vs} \ O(n!)}$
# Comparación 4
plt.figure(figsize=(8,5))
plt.plot(n_range_4, Oa_power_n(n_range_4, a=2), label="O(2^n)", linewidth=2, color ='royalblue')
plt.plot(n_range_4, On_factorial(n_range_4), label="O(n!)", linewidth=2, color ='blueviolet')
plt.yscale("log") # Escala logarítmica para ver ambas curvas
plt.xlabel("n (ej. número de genes)")
plt.ylabel("Tiempo relativo (escala log)")
plt.title("O(2^n) vs O(n!)", fontsize=12, fontweight='bold')
plt.legend()
plt.grid(True, which="both")
plt.show()
Discusión
Los algoritmos de complejidad exponencial y factorial, como $O(2^n)$ y $O(n!)$, crecen de manera extremadamente rápida, lo que los vuelve inviables en la práctica para valores grandes de $n$. En genética, por ejemplo, $O(2^n)$ puede representar las combinaciones posibles de mutaciones binarias, mientras que $O(n!)$ puede modelar el número de formas de ordenar $n$ genes distintos, ilustrando cómo estos algoritmos escapan rápidamente de cualquier capacidad de cómputo razonable. Por otro lado, al comparar complejidades polinómicas, $O(n^2)$ crece mucho más rápido que $O(n \log n)$, lo que evidencia que los algoritmos cuadráticos, aunque manejables en problemas pequeños, se vuelven imprácticos para datasets de gran escala. Estas diferencias subrayan la importancia de elegir cuidadosamente la estrategia algorítmica en función del tamaño de los datos y la factibilidad de su ejecución computacional (Cormen et. al., 2022).
- $\mathbf{O(n!) \ \text{vs} \ O(n^n)}$
# Comparación 5
plt.figure(figsize=(8,5))
plt.plot(n_range_5, On_factorial(n_range_5), label="O(n!)", linewidth=2, color ='royalblue')
plt.plot(n_range_5, On_power_n(n_range_5), label="O(n^n)", linewidth=2, color ='blueviolet')
plt.yscale("log")
plt.xlabel("n (ej. estados cuánticos posibles)")
plt.ylabel("Tiempo relativo (escala log)")
plt.title("O(n!) vs O(n^n)", fontsize=12, fontweight='bold')
plt.legend()
plt.grid(True, which="both")
plt.show()
Discusión
La complejidad $O(n^n)$ crece incluso más rápido que $O(n!)$, alcanzando magnitudes astronómicas que exceden por mucho cualquier capacidad de cómputo práctica. En física cuántica, este comportamiento puede ilustrar el crecimiento del número de estados posibles en un sistema con $n$ partículas, cada una con $n$ estados disponibles, lo que genera un espacio de posibilidades prácticamente imposible de procesar. Al mismo tiempo, incluso dentro de las complejidades polinómicas, la diferencia entre un algoritmo constante $O(1)$ y uno cuadrático $O(n^2)$ resulta abismal, ya que para valores grandes de $n$, $O(n^2)$ puede ser millones de veces más costoso que $O(1)$. Estas comparaciones destacan cómo la tasa de crecimiento de los algoritmos impacta directamente en su viabilidad y refuerzan la necesidad de preferir aquellos con baja complejidad para aplicaciones en las que se manejan volúmenes masivos de datos (Cormen et. al., 2022).
5. Creación de una tabla que muestra tiempos de ejecución simulados para algoritmos ficticios que para ejecutarse requieren un número de operaciones gobernado por cada una de las funciones que representan los ordenes siguientes:
$O(1),O(logn),O(\sqrt{n}),O(n^{2}),O(2^{n}),O(n!),O(n^{n}),O(n^{n^{n}})$
suponiendo que cada operación tiene un costo de 1 nanosegundo.
Nota:
En el análisis de complejidad de algoritmos, el número de operaciones crece muy rápido para órdenes exponenciales o factoriales, debido a esto se utilizará logaritmo base 10 y en el caso de la función factorial, se aplicará la Aproximación de Stirling:
Esta aproximación permite estimar el factorial de un número grande $n$ sin calcular todos los productos:
$n! \approx \sqrt{2 \pi n} (\frac{n}{e})^{n}$
Para análisis de complejidad, se suele usar el logaritmo base 10:
$\log_{10}{n!} \approx 0.5 \log_{10}{2 \pi n} + n \log_{10}{n} - n \log_{10}{e}$
Es decir,
- $n \log_{10}{n}$ domina el crecimiento del factorial.
- La corrección $0.5 \log_{10}{2\pi n}$ mejora la precisión.
- Esta aproximación es más exacta cuanto mayor es $n$.
(Stirling J., 1730).
# Factorial exacto para n pequeños, aproximación Stirling para n grandes
def On_factorial(n):
# Si n < 100 se hace el cálculo exacto
if n < 100:
return factorial(n)
else:
# Usamos log10(Stirling) y regresamos 10**valor aproximado
log10_val = n*log10(n) - n*log10(e) + 0.5*log10(2*pi*n)
return 10**log10_val
# Se definen las funciones para calcular log10(#operaciones) de distintos órdenes
# de complejidad
def log10_O1(n):
# Complejidad constante O(1), siempre 1 operación → log10(1) = 0
return 0
def log10_Ologn(n):
# Complejidad logarítmica O(log n) → log10(log2(n))
return log10(np.log2(n))
def log10_On_sqrt(n):
# Complejidad O(√n) → log10(sqrt(n)) = 0.5*log10(n)
return 0.5*log10(n)
def log10_On2(n):
# Complejidad cuadrática O(n^2) → log10(n^2) = 2*log10(n)
return 2*log10(n)
def log10_O2n(n):
# Complejidad exponencial O(2^n) → log10(2^n) = n*log10(2)
return n*log10(2)
def log10_On_factorial(n):
# Complejidad factorial O(n!)
# Para n pequeño usamos factorial exacto, para n grande usamos aproximación de Stirling
if n < 100:
return log10(factorial(n))
else:
# Se aplica la aproximación de Stirling:
return n*log10(n) - n*log10(e) + 0.5*log10(2*pi*n)
def log10_On_power_n(n):
# Complejidad O(n^n) → log10(n^n) = n*log10(n)
return n*log10(n)
def log10_On_power_n_power_n(n):
# Aproximación para O(n^(n^n))
# log10(n^(n^n)) ≈ n * n * log10(n)
return n * n * log10(n)
# Indicamos los tamaños de entrada
n_values = [10, 100, 1000, 10000]
tabla = []
for n in n_values:
# Creamos un diccionario para cada fila de la tabla
fila = {"n": n}
# Diccionario de funciones:
funciones = {
"O(1)": log10_O1,
"O(log n)": log10_Ologn,
"O(√n)": log10_On_sqrt,
"O(n^2)": log10_On2,
"O(2^n)": log10_O2n,
"O(n!)": log10_On_factorial,
"O(n^n)": log10_On_power_n,
"O(n^(n*n))": log10_On_power_n_power_n,
}
for nombre, f in funciones.items():
# Se calcula el log10 del número de operaciones
log_val = f(n)
# Para valores muy grandes, se aplica la notación 10^x
if nombre in ["O(2^n)", "O(n!)", "O(n^n)", "O(n^(n*n))"]:
fila[nombre] = f"10^{log_val:.1f}"
else:
# Para valores pequeños, se muestran enteros
fila[nombre] = int(round(10**log_val))
# Se añade la fila a la tabla
tabla.append(fila)
# Se muestra la tabla con los valores obtenidos en un DataFrame
df = pd.DataFrame(tabla)
# Usamos 'n' como índice
df = df.set_index("n")
df
| O(1) | O(log n) | O(√n) | O(n^2) | O(2^n) | O(n!) | O(n^n) | O(n^(n*n)) | |
|---|---|---|---|---|---|---|---|---|
| n | ||||||||
| 10 | 1 | 3 | 3 | 100 | 10^3.0 | 10^6.6 | 10^10.0 | 10^100.0 |
| 100 | 1 | 7 | 10 | 10000 | 10^30.1 | 10^158.0 | 10^200.0 | 10^20000.0 |
| 1000 | 1 | 10 | 32 | 1000000 | 10^301.0 | 10^2567.6 | 10^3000.0 | 10^3000000.0 |
| 10000 | 1 | 13 | 100 | 100000000 | 10^3010.3 | 10^35659.5 | 10^40000.0 | 10^400000000.0 |
6. Discusión de las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información.
La tabla presentada muestra los tiempos simulados para distintos órdenes de complejidad algorítmica considerando que cada operación toma 1 nanosegundo. A partir de estos resultados se pueden extraer varias conclusiones importantes respecto al manejo de grandes volúmenes de información:
\subsection*{Los algoritmos de baja complejidad crecen lentamente}
Para $O(1)$ y $O(\log n)$, incluso al aumentar $n$ hasta 10,000, los tiempos de ejecución permanecen manejables (1 a 13 ns).
Esto demuestra que algoritmos con complejidad constante o logarítmica son altamente eficientes para grandes volúmenes de datos.
\subsection*{La complejidad polinómica conlleva un crecimiento acelerado}
En el caso de $O(n^2)$, el tiempo de ejecución aumenta de manera significativa con $n$, llegando a 100 millones de ns para $n = 10000$.
Aunque sigue siendo computable, se evidencia que algoritmos cuadráticos o de mayor orden polinómico se vuelven prohibitivos cuando el tamaño de los datos crece, limitando su aplicabilidad en datasets masivos (Han, et. al.,2011).
\subsection*{Algoritmos exponenciales y factoriales: inviabilidad práctica}
Para $O(2^n)$, $O(n!)$ y órdenes superiores como $O(n^n)$ o $O(n^{n^n})$, los tiempos simulados se disparan rápidamente, alcanzando cifras astronómicas (por ejemplo, $O(n!) \approx 10^{35659}\ \text{ns}$ para $n=10000$.
Esto demuestra que estos algoritmos son prácticamente imposibles de ejecutar para datos grandes, aun considerando mejoras tecnológicas futuras. Su uso se restringe a valores muy pequeños de $n$.
\subsection*{Importancia de la elección de algoritmos}
La comparación entre las diferentes complejidades enfatiza la necesidad de seleccionar algoritmos eficientes para aplicaciones de big data y procesamiento masivo de información (Dean et. al., 2008).
Incluso pequeñas diferencias en el orden de complejidad tienen un impacto enorme en los tiempos de cómputo cuando $n$ es grande, lo que puede traducirse en costos significativos de hardware y energía (Cormen et. al. 2022).
Conclusión
Los resultados de la simulación muestran con claridad cómo el crecimiento de los tiempos de ejecución depende fuertemente del orden de complejidad del algoritmo. Complejidades bajas como $O(1)$, $O(logn)$ y $O(\sqrt{n})$ permanecen prácticamente constantes o con incrementos muy leves incluso cuando el tamaño de los datos pasa de $n=10$ a $n=10,000$. Este comportamiento evidencia que algoritmos de este tipo resultan ideales para aplicaciones en las que se procesan grandes volúmenes de información, ya que escalan de manera eficiente sin un impacto significativo en los recursos computacionales.
En contraste, algoritmos de complejidad polinómica como $O(n^{2})$ muestran un aumento mucho más evidente: al llegar a $n=10,000$, los tiempos simulados alcanzan $10^{8}$ nanosegundos, lo que, aunque computable, refleja limitaciones prácticas para conjuntos de datos aún mayores. Por su parte, las complejidades exponenciales y factoriales, como $O(2^{n})$, $O(n!)$ y $O(n^{n})$, se disparan de manera abrupta, lo cual, incluso para valores relativamente pequeños de $n$, generan cifras astronómicas imposibles de manejar en la práctica. Esto refleja que dichos algoritmos son teóricamente relevantes, pero su aplicabilidad real queda restringida a casos muy pequeños o de naturaleza combinatoria particular.
Finalmente, al considerar el comportamiento asintótico cuando $n \rightarrow ∞$, las diferencias se vuelven aún más drásticas: algoritmos constantes y logarítmicos siguen siendo viables, mientras que los polinómicos de bajo grado se vuelven cada vez más costosos, y los exponenciales o factoriales resultan completamente inviables. Estas simulaciones confirman que la selección de algoritmos eficientes no solo es una cuestión académica, sino un requisito indispensable para el diseño de sistemas capaces de manejar escenarios de big data, biología computacional o física cuántica, donde el tamaño de los datos y la complejidad de los problemas pueden crecer de forma extrema (Cormen et al., 2022).
Referencias
Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data structures and algorithms. Addison-Wesley.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press.
Knuth, D. E. (1976). Big omicron and big omega and big theta. ACM SIGACT News, 8(2), 18–24.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Stirling, J. (1730). Methodus Differentialis. Londres.
Han, J., Pei, J., & Kamber, M. (2011). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.
Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, 51(1), 107–113.