1A. Reporte escrito. Introducción al análisis de algoritmos.

Author

José Alberto Villegas Díaz Disciplina.

Lista de Cambios:

Se corrigió puntuación y ortografía.

Se dio formato de ecuación a expresiones matemáticas.

Se corrigió tabla 1.

Se dio más profundidad a la discusión de los experimentos.

Introducción

Un algoritmo es cualquier procedimiento computacional bien definido que toma un valor, o conjunto de valores, como entrada y produce un valor, o conjunto de valores, como salida (Cormen et al. 2022). En las ciencias de la computación el análisis de un algoritmo significa predecir los recursos que el algoritmo requiere. La mayoría de las veces es el tiempo computacional lo que queremos medir, para esto nos apoyamos del orden de crecimiento (Cormen et al. 2022). El orden de crecimiento es una forma de describir cómo cambia el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de la entrada. En otras palabras, nos ayuda a entender la eficiencia de un algoritmo en función de la cantidad de datos con los que trabaja.

El objetivo de este reporte es realizar una comparación gráfica de distintos órdenes de crecimiento así como la elaboración de una tabla que nos permitirá comparar tiempos de ejecución simulados para algoritmos ficticios que tengan los órdenes de crecimiento de las funciones graficadas. Esto nos brindará una mejor comprensión de los costos de cómputo asociados con el manejo de grandes cantidades de información

using Plots
using LaTeXStrings

Figura 1. \(O(1)\) vs \(O(log n)\)

n = 300 # 300 puntos

plot(1:n, [1 for x in 1:n], label=L"1")
plot!(1:n, [log2(x) for x in 1:n], label=L"\log{n}")

De la figura 1 podemos observar que para una complejidad constante \(O(1)\), el tiempo de ejecución o el uso de recursos es independiente del tamaño de la entrada. Esto significa que el algoritmo siempre ejecutará la misma cantidad de operaciones, sin importar cuán grande sea el conjunto de datos. Por esta razón, los algoritmos con complejidad constante son extremadamente eficientes y escalables, ya que el costo de procesamiento permanece fijo sin importar el tamaño de la entrada.

Para una complejidad logarítmica \(O(\log n)\), el tiempo de ejecución crece de manera logarítmica respecto al tamaño de la entrada. Esto quiere decir que, aunque el tiempo aumenta conforme crece el tamaño de los datos, el ritmo de este incremento disminuye a medida que la entrada es más grande. En otras palabras, el crecimiento es muy lento en comparación con otras complejidades más elevadas. Por ello, los algoritmos con complejidad logarítmica también son considerados eficientes y adecuados para manejar entradas muy grandes, ya que el aumento en el tiempo de ejecución es relativamente bajo incluso para valores de \(n\) muy grandes.

Figura 2. \(O(n)\) vs \(O(nlogn)\)

using Plots
using LaTeXStrings
n = 300 # 300 puntos

plot(1:n, [n*log2(x) for x in 1:n], label=L"n\log{n}")
plot!(1:n, [x for x in 1:n], label=L"n")

De la figura 2 se aprecia que la complejidad \(O(n)\) crece de manera lineal, lo que significa que el tiempo de ejecución del algoritmo aumenta proporcionalmente al tamaño de la entrada. Por ejemplo, si duplicamos el tamaño de los datos de entrada, el tiempo necesario para procesarlos también se duplicará aproximadamente. Esto sucede porque cada elemento de la entrada se procesa una sola vez, sin operaciones adicionales que dependan de otros elementos. Por esta razón, los algoritmos con complejidad lineal son generalmente eficientes y escalables para conjuntos de datos grandes, siempre que el crecimiento del tamaño no sea excesivo.

En el caso de la complejidad \(O(n \log n)\), el tiempo de ejecución también crece en función del tamaño de la entrada, pero incorpora un factor adicional logarítmico. Esto significa que, además de procesar cada elemento una vez, el algoritmo realiza operaciones adicionales cuyo número crece de forma logarítmica respecto al tamaño de la entrada. Por ejemplo, muchos algoritmos de ordenamiento eficientes, como el mergesort o el heapsort, tienen esta complejidad porque dividen la entrada en partes más pequeñas y luego combinan los resultados. Como resultado, aunque el tiempo crece más rápido que en el caso lineal, sigue siendo mucho más eficiente que una complejidad cuadrática o cúbica, especialmente para entradas grandes.

Figura 3. \(O(n^2)\) vs \(O(n^3)\)

n = 100 # 100 puntos
plot(1:n, [x^2 for x in 1:n], label=L"n^2")
plot!(1:n, [x^3 for x in 1:n], label=L"n^3")

De la figura 3, observamos que, si bien, ambas complejidades son polinómicas, pero a pesar de ello, la diferencia, aunque sea de un solo grado en el polinomio, implica un crecimiento mucho mayor para \(n^3\) a partir de valores moderados de \(n\).

La complejidad \(n^2\) podría ser eficiente para entradas pequeñas y moderadas, ya que el tiempo de ejecución crece proporcionalmente al cuadrado del tamaño de la entrada. Sin embargo, \(n^3\) crece de forma mucho más rápida, lo que hace que los algoritmos con esta complejidad solo sean prácticos para entradas pequeñas.

Por lo tanto, incluso un pequeño aumento en el grado del polinomio puede tener un impacto significativo en la escalabilidad y eficiencia del algoritmo conforme el tamaño de la entrada aumenta.

Figura 4. \(O(a^n)\) vs \(O(n!)\)

n = 7 # A partir de este punto se vuelve impráctico manejar entradas grandes o incluso moderadas. A partir de 20 arroja un error de sobreflujo. 

plot(1:n, [2^x for x in 1:n], label=L"a^n") #Se utilizó a=2, para comparar los alcances de la complejidad incluso con una constante pequeña
plot!(1:n, [factorial(x) for x in 1:n], label=L"n!")

La figura 4, demuestra que las complejidades exponencial y factorial demuestran ser ineficientes incluso para valores de entrada moderados.

Nótese que en la complejidad exponencial, se manejó \(a=2\) por lo que está representada por \(O(2^n)\) o similar. Se observa que crece de manera extremadamente rápida conforme aumenta el tamaño de la entrada, lo que hace que el tiempo de ejecución se vuelva prohibitivo para valores medianos o grandes de \(n\).

Por otro lado, la complejidad factorial, \(O(n!)\), crece aún más rápido que la exponencial, ya que el número de operaciones necesarias aumenta de forma factorial con el tamaño de la entrada. Esto la convierte en la opción menos eficiente y prácticamente impracticable para cualquier tamaño de entrada que no sea muy pequeño.

En resumen, ambos tipos de complejidad son inviables para aplicaciones con entradas de tamaño moderado o grande debido a su crecimiento acelerado en el uso de tiempo y recursos.

Figura 5. \(O(n!)\) vs \(O(n^n)\)

n = 5

plot(1:n, [x^x for x in 1:n], label=L"n^n")
plot!(1:n, [factorial(x) for x in 1:n], label=L"n!")

En la figura 5 al igual que en la figura 3, podemos observar que ambas complejidades son altamente ineficientes debido a que su tasa de crecimiento es muy acelerada. Nótese que \(n\) se tuvo que limitar 5.

En particular, la complejidad \(O(n^n)\) crece aún más rápido que la factorial \(O(n!)\), lo que significa que el número de operaciones necesarias para procesar la entrada se dispara rápidamente incluso para valores muy pequeños de \(n\).

Esta tasa de crecimiento extremadamente alta limita el uso práctico de algoritmos con estas complejidades únicamente a entradas muy pequeñas, ya que para tamaños moderados o grandes, el tiempo de ejecución se vuelve prohibitivo.

Tabla de simulación de tiempos de ejecución

Construiremos una tabla donde muestre tiempos de ejecución simulados para algoritmos ficticios que tengan los órdenes de crecimiento anteriores, suponiendo que cada operación tiene un costo de 1 nanosegundo.

#Primero crearemos la tabla
# Valores de n
n_values = [100, 1000, 10000, 100000]

# Funciones de complejidad y sus tiempos en nanosegundos
execution_times = [
    ("O(1)", [1, 1, 1, 1]),                           # Constante
    ("O(log n)", [floor(Int, log2(n)) for n in n_values]), # Logarítmico
    ("O(n)", [n for n in n_values]),                  # Lineal
    ("O(n log n)", [n * floor(Int, log2(n)) for n in n_values]), # n log n
    ("O(n^2)", [n^2 for n in n_values]),              # Cuadrático
    ("O(n^3)", [n^3 for n in n_values]),              # Cúbico
    ("O(n!)", [factorial(big(n)) for n in n_values if n <= 10]), # Factorial. Se limita el alcance de n. 
    ("O(n^n)", [big(n)^n for n in n_values if n <= 10])          # n^n. Se limita el alcance de n.
]

# Imprimir encabezado
println("| Función     | n=100     | n=1000     | n=10000     | n=100000     |")
println("|-------------|-----------|------------|-------------|--------------|")

# Formatear e imprimir filas
for (name, times) in execution_times
    # Ajustar filas para entradas faltantes si el tamaño es menor a n_values
    row = [name]  # Primera columna
    for time in times
        push!(row, string(time))
    end
    # Completar con espacios en blanco si faltan columnas
    while length(row) < 5
        push!(row, "-")
    end
    println("| ", join(row, " | "), " |")
end

| Función     | n=100     | n=1000     | n=10000     | n=100000     |
|-------------|-----------|------------|-------------|--------------|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 6 | 9 | 13 | 16 |
| O(n) | 100 | 1000 | 10000 | 100000 |
| O(n log n) | 600 | 9000 | 130000 | 1600000 |
| O(n^2) | 10000 | 1000000 | 100000000 | 10000000000 |
| O(n^3) | 1000000 | 1000000000 | 1000000000000 | 1000000000000000 |
| O(n!) | - | - | - | - |
| O(n^n) | - | - | - | - |

Tabla 1.Crecimiento de Funciones de Complejidad para Diferentes Tamaños de Entrada \(n\)

\[ \begin{array}{|c|c|c|c|c|} \hline \textbf{Función} & n=100 & n=1000 & n=10000 & n=100000 \\ \hline O(1) & 1 & 1 & 1 & 1 \\ O(\log n) & 6 & 9 & 13 & 16 \\ O(n) & 100 & 10^3 & 10^4 & 10^5 \\ O(n \log n) & 6 \times 10^2 & 9 \times 10^3 & 1.3 \times 10^5 & 1.6 \times 10^6 \\ O(n^2) & 10^3 & 10^6 & 10^8 & 10^{10} \\ O(n^3) & 10^6 & 10^9 & 10^{12} & 10^{15} \\ O(n!) & \infty & \infty & \infty & \infty \\ O(n^n) & \infty & \infty & \infty & \infty \\ \hline \end{array} \]

Valores aproximados del crecimiento temporal para distintas funciones de complejidad en función del tamaño de la entrada \(n\). Se muestra cómo aumentan los costos computacionales desde complejidades constantes hasta exponenciales y factoriales, utilizando notación científica para facilitar la comparación en rangos grandes de \(n\).

Conclusiones

Después de la comparación y simulación se puede concluir que los órdenes de complejidad de los algoritmos, impactan directamente en los tiempos de procesamiento. Del ejercicio podemos identificar que los algoritmos de complejidades \(O(1)\), \(O(log n)\) o incluso \(O(n)\), tienden a escalar bien independientemente del número de entradas, mientras que los algoritmos de complejidades \(O(n log n)\), \(O(n^2)\), \(O(n^3)\) están más acotados a entradas pequeñas a moderadas, y finalmente los algoritmos de complejidad \(O(n!)\) y \(O(n^n)\), son demasiado límitados a entradas extremadamente pequeñas.

Resulta entonces imperativo tener conocimiento de las complejidades que pueden tener los algoritmos ya que esto facilitará la elección de los adecuados para mitigar los costos y optimizar el tiempo de procesamiento.

Bibliografía

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press.