2 Introducción al análisis de algoritmos con Julia

Este capítulo introduce los fundamentos de análisis de algoritmos. Se introduce el concepto de modelo de cómputo, se itroduce y se motiva la notación asintótica, ya que es el lenguaje común en el análisis de algoritmos. También se mostrarán algunos de los ordenes de crecimiento más representativos, que nos permitirán comparar algoritmos que resuelvan una tarea dada, así como permitirnos catalogarlos con respecto a los recursos de computo necesarios para ejecutarlos.

2.1 Concepto de algoritmo y estructura de datos

Los algoritmos son especificaciones formales de los pasos u operaciones que deben aplicarse a un conjunto de entradas para resolver un problema, obteniendo una solución correcta a dicho problema. Establecen los fundamentos de la programación y de la manera en como se diseñan los programas de computadoras. Dependiendo del problema, pueden existir múltiples algoritmos que lo resuelvan, cada uno de ellos con sus diferentes particularidades. Así mismo, un problema suele estar conformado por una cantidad enorme de instancias de dicho problema, por ejemplo, para una lista de $n$ números, existen $n!$ formas de acomodarlos, de tal forma que puedan ser la entrada a un algoritmo cuya entrada sea una lista de números donde el orden es importante. En ocasiones, los problemas pueden tener infinitas de instancias. En este curso nos enfocaremos en problemas que pueden ser simplificados a una cantidad finita instancias.

Cada paso u operación en un algoritmo esta bien definido y puede ser aplicado o ejecutado para producir un resultado. A su vez, cada operación suele tener un costo, dependiente del módelo de computación. Conocer el número de operaciones necesarias para transformar la entrada en la salida esperada, i.e., resolver el problema, es de vital importancia para seleccionar el mejor algoritmo para dicho problema, o aun más, para instancias de dicho problema que cumplen con ciertas características.

Una estructura de datos es una abstracción en memoria de entidades matemáticas y lógicas que nos permite organizar, almacenar y procesar datos en una computadora. El objetivo es que la información representada puede ser manipulada de manera eficiente en un contexto específico, además de simplificar la aplicación de operaciones para la aplicación de algoritmos.

2.2 Modelos de cómputo

Un modelo de cómputo es una abstracción matemática de una computadora o marco de trabajo algorítmico que nos permite estudiar y medir los costos de los algoritmos funcionando en este modelo de tal forma que sea más simple que una computadora física real. Ejemplos de estos modelos son las máquinas de Turing, las funciones recursivas, el cálculo lambda, o la máquina de acceso aleatorio. Todas estos modelos son equivalentes en sus capacidades, pero sus diferentes planteamientos permiten enfocarse en diferentes aspectos de los problemas.

La máquina de Turing. Es un módelo creado por Alan Turing a principios del siglo XX; la idea es un dispositivo que podría ser implementada de manera mecánica si se tuvieran recursos infinitos; esta máquina puede leer y escribir en una cinta infinita una cantidad de símbolos predeterminada para cada problema siguiendo una serie de reglas simples sobre lo que lee y escribe, dichas reglas y la cienta, forman una máquina de estados y memoria, que pueden realizar cualquier cálculo si el tiempo no fuera un problema.
Funciones recursivas. Se basa en funciones que trabajan sobre los números naturales y que definen en conjunto el espacio de funciones computables. Son una herramienta abstracta que permite a los teóricos de la lógica y computación establecer los límites de lo computable.
Cálculo lambda. Es un módelo creado por Alonzo Church y Stephen Kleene a principios del siglo XX, al igual que las funciones recursivas, se fundamenta en el uso de funciones y es una herramienta abstracta con própositos similares, sin embargo el cálculo lambda no se limita a recursiones, y se enfoca en diferentes reglas de reducción y composición de funciones, y es natural la inclusión de operadores de alto nivel, aunque estos mismos sean definidos mediante un esquema funcional.
Máquina de acceso aleatorio (RAM). Es un módelo que describe una computadora con registros. Adiferencia de una computadora física, no tienen limitación en su capacidad, ni en la cantidad de registros ni en la precisión de los mismos. Cada registro puede ser identicado de manera única y su contenido leído y escrito mediante reglas o instrucciones formando un programa. En particular reconoce las diferencias entre registros de los programas y registros de datos, i.e., arquitectura harvard. Existe un número mínimo de instrucciones necesarias (i.e., incremento, decremento, poner a cero, copiar, salto condicional, parar) pero es común construir esquemas más complejos basados en estas primitivas. Se necesita un registro especial que indica el registro de programa siendo ejecutado. Los accesos a los registros tienen un tiempo constante a diferencia de otros esquemas; es el modelo más cercano a una implementación moderna de computadora.

Una computadora moderna difiere de muchas formas de una máquina RAM. De entrada, las limitaciones físicas requieren memorias finitas y registros con valores mínimos y máximos. También se debe trabajar con una jerarquía de memoria con diferentes niveles, donde los niveles más rápidos también son los más escasos; por tanto, es importante sacar provecho de esta jerarquía siempre que sea posible. Las operaciones también tienen costos diferentes, dependiendo de su implementación a nivel de circuitería, así como también existe cierto nivel de paralelización que no esta presente en una máquina RAM, tanto a nivel de procesamiento de datos como lectura de datos y el programa, esto sin tener en cuenta la arquitecturas multitarea que ya es común en el equipo actual.

En este curso nos enfocaremos en especificaciones de alto nivel, donde los algoritmos pueden ser implementados en una computadora física, y estaremos contando operaciones de interés pensando en costos constantes en el acceso a memoria y en una selección de operaciones, al estilo de una máquina RAM.

La selección de operaciones de interés tiene el espíritu de simplificar el análisis, focalizando nuestros esfuerzos en operaciones que acumulan mayor costo y que capturan la dinámica del resto. Adicionalmente al conteo de operaciones nos interesa el desempeño de los algoritmos en tiempo real y en la cantidad de memoria consumida, por lo que se aboradará el costo realizando mediciones experimentales, contrastando con el análisis basado en conteo de operaciones siempre que sea posible.

2.3 Tipos de análisis

La pregunta inicial sería ¿qué nos interesa saber de un algoritmo que resuelve un problema? probablemente, lo primero sería saber si produce resultados correctos. Después, entre el conjunto de las alternativas que producen resultados correctos, es determinante obtener su desempeño para conocer cuál es más conveniente para resolver un problema.

En ese punto, es necesario reconocer que para un problema, existen diferentes instancias posibles, esto es el espacio de instancias del problema, y que cada una de ellas exigirían soluciones con diferentes costos para cada algoritmo. Por tanto existen diferentes tipos de análisis y algoritmos.

Análisis de mejor caso. Obtener el mínimo de resolver cualquier instancia posible, puede parecer poco útil desde el punto de vista de decisión para la selección de un algoritmo, pero puede ser muy útil para conocer un problema o un algoritmo.
Análisis de peor caso. Obtener el costo máximo necesario para resolver cualquier instancia posible del problema con un algoritmo, este es un costo que si nos puede apoyar en la decisión de selección de un algoritmo; sin embargo, en muchas ocasiones, puede ser poco informativo o innecesario ya que tal vez hay pocas instancias que realmente lo amériten.
Análisis promedio. Se enfoca en obtener un análisis promedio basado en la población de instancias del problema para un algoritmo dado.
Análisis amortizado. Se enfoca en análisis promedio pero para una secuencia de instancias.
Análisis adaptativo. Para un subconjunto bien caracterizado del espacio de instancias de un problema busca análizar los costos del algoritmo en cuestión. La caracterización suele estar en términos de una medida de complejidad para el problema; y la idea general es medir si un algoritmo es capaz de sacar provecho de instancias fáciles.

2.4 Notación asintótica

Realizar un conteo de operaciones y mediciones es un asunto complejo que requiere focalizar los esfuerzos. Para este fin, es posible contabilizar solo algunas operaciones de importancia, que se supondrían serían las más costosas o que de alguna manera capturan de manera más fiel la dinámica de costos.

El comportamiento asintótico es otra forma de simplificar y enfocarnos en los puntos de importancia, en este caso, cuando el tamaño de la entrada es realmente grande. Es importante mencionar, que no se esperan entradas de tamaño descomunal, ni tampoco se espera cualquier tipo de entrada.

2.4.1 Notación $\Theta$

Para una función dada $g(n)$ denotamos por $\Theta(g(n))$ el siguiente conjunto de funciones:

\[\begin{align} \Theta(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c_1, c_2 \text{ y } n_0 \text{ tal que } \right.\\ ~ & \left. 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

esto es, una función $f(n)$ pertenece al conjunto $g(n)$ si $c_1 g(n)$ y $c_2 g(n)$ pueden cubrirla por abajo y por arriba, para esto deben existen las constantes positivas $c_1$ y $c_2$ y una $n$ lo suficientemente larga, e.g., para eso la constante $n_0$. La notación propiamente de conjuntos puede usarse $f(n) \in \Theta(g(n))$ pero es común en el área usar $f(n) = \Theta(g(n))$ para expresar la pertenencia; este abuso de la notación tiene ventaja a la hora de plantear los problemas de análisis.

2.4.2 Notación $O$

Se utiliza para indicar una cota asintótica superior. Una función $f(n)$ se dice que esta en $O(g(n))$ si esta en el siguiente conjunto:

\[\begin{align} O(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right.\\ ~& \left. 0 \leq f(n) \leq c g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

La notación $O$ se usa para dar una cota superior, dentro de un factor constante. Al escribir $f(n) = O(g(n))$ se indica que $f(n)$ es miembro del conjunto $O(g(n))$; hay que notar que $f(n) = \Theta(g(n))$ implica que $f(n) = O(g(n))$, i.e., $\Theta(g(n)) \subseteq O(g(n))$.

2.4.3 Notación $\Omega$

Al contrario de $O$, la notación $\Omega$ da una cota asintótica inferior. Una función $f(n)$ se dice que esta en $\Omega(g(n))$ si esta en el siguiente conjunto:

\[\begin{align} \Omega(g(n)) = & \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right. \\ & \left. 0 \leq c g(n) \leq f(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align}\]

Dado que la $\Omega$ define una cota superior, basicamente si $f(n) = \Omega(g(n))$, entonces $f(n)$ debe estar por encima de $g(n)$ con las constantes $c$ y $n_0$ adecuadas. Al igual que la notación $O$, la notación $\Omega$ es menos estricta que $\Theta$, esto es $f(n) = \Theta(g(n))$ implica que $f(n) = \Omega(g(n))$, por lo que $\Theta(g(n)) \subseteq \Omega(g(n))$.

Por tanto, si $f(n) = O(g(n))$ y $f(n) = \Omega(g(n))$ entonces $f(n) \in \Theta(g(n))$.

Es importante conocer los ordenes de crecimiento más comunes de tal forma que podamos realizar comparaciones rápidas de costos, y dimensionar las diferencias de recursos entre diferentes tipos de costos. La notación asintótica hace uso extensivo de la diferencia entre diferentes ordenes de crecimiento para ignorar detalles y simplificar el análisis de algoritmos.

2.4.4 Apoyo audio-visual

En los siguientes videos se profundiza sobre los modelos de cómputo y los diferentes tipos de análisis sobre algoritmos.

Parte 1:
Parte 2:
Parte 3:

2.4.5 Ordenes de crecimiento

Dado que la idea es realizar un análisis asintótico, las constantes suelen ignorarse, ya que cuando el tamaño de la entrada es suficientemente grande, los términos con mayor orden de magnitud o crecimiento dominarán el costo. Esto es, es una simplificación necesaría.

Los ordenes de crecimiento son maneras de categorizar la velocidad de crecimiento de una función, y para nuestro caso, de una función de costo. Junto con la notación asimptótica nos permite concentrarnos en razgos gruesos que se mantienen para entradas grandes, más que en los detalles, y no perder el punto de interés. A continuación veremos algunas funciones con crecimientos paradigmáticos; las observaremos de poco en poco para luego verlos en conjunto.

2.4.5.1 Costo constante, logaritmo y lineal

La siguiente figura muestra un crecimiento nulo (constante), logaritmico y lineal. Note como la función logarítmica crece lentamente.

using Plots, LaTeXStrings
n = 300 # 300 puntos

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

2.4.5.2 Costo $n \log n$ y polinomial

A continuación veremos tres funciones, una función con $n\log n$ y una función cuadrática y una cúbica. Note como para valores pequeños de $n$ las diferencias no son tan apreciables para como cuando comienza a crecer $n$; así mismo, observe los valores de $n$ de las figuras previas y de la siguiente, este ajuste de rangos se hizo para que las diferencias sean apreciables.

n = 7 # note que se usan menos puntos porque 300 serían demasiados para el rango

plot(1:n, [x * log2(x) for x in 1:n], label=L"n\log_2{n}")
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")

2.4.5.3 Exponencial

A continuación se compara el crecimiento de una función exponencial con una función polinomial. Note que la función polinomial es de grado 4 y que la función exponencial tiene como base 2; aún cuando para números menores de aproximadamente 16 la función polinomial es mayor, a partir de ese valor la función $2^n$ supera rapidamente a la polinomial.

n = 20

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

2.4.5.4 Crecimiento factorial

Vease como la función factorial crece mucho más rápido que la función exponencial para una $n$ relativamente pequeña. Vea las magnitudes que se alcanzan en el eje $y$, y comparelas con aquellas con los anteriores crecimientos.

n = 20

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

2.4.5.5 Un poco más sobre funciones de muy alto costo

n = 10

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

Vea la figura anterior, donde se compara $n!$ con $n^n$, observe como es que cualquier constante se vuelve irrelevante rapidamente; aun para $n^n$ piense en $n^{n^n}$.

Note que hay problemas que son realmente costosos de resolver y que es necesario conocer si se comporta así siempre, si es bajo determinado tipo de entradas. Hay problemas en las diferentes áreas de la ciencia de datos, donde veremos este tipo de costos, y habrá que saber cuando es posible solucionarlos, o cuando se deben obtener aproximaciones que nos acerquen a las respuestas correctas con un costo manejable, es decir, mediar entre exactitud y costo. En este curso se abordaran problemas con un costo menor, pero que por la cantidad de datos, i.e., $n$, se vuelven muy costosos y veremos como aprovechar supuestos como las distribuciones naturales de los datos para mejorar los costos.

2.5 El enfoque experimental

La notación asintótica nos permite alcanzar un lenguaje común y preciso sobre los costos de problemas y algoritmos; es de especial importancia para la evaluación de las alternativas en la literatura especializada, y elegir algoritmos aún sin la necesidad de implementación. El análisis asintótico da la posibilidad de conocer el desempeño desde diferentes perspectivas como peor caso o caso promedio, utilizando un módelo de computación, y siempre pensando en entradas lo suficientemente grandes.

En la práctica, existe una múltitud de razones por los cuales los problemas que se resuelven podrian no ser tan grandes como para que un algoritmo domine a otros de manera asintótica, las instancias podrían no ser tan generales como para preocuparse en el peor caso, o el caso promedio general. En muchas situaciones, es importante sacar provecho de los casos fáciles, sobre todo cuando el problema a resolver podría asegurar que dichos casos simples sean abundantes. Dada la complejidad detrás de definir sub-conjuntos de instancias y llevar a cabo un análisis formal, se vuelve imperativo realizar pruebas experimentales.

Por otra parte, dada la complejidad de una computadora moderna, es necesario realizar evaluaciones experimentales de los algoritmos que tengan una complejidad similar. Las computadoras reales tienen una jerarquia de memoria con tamaños y velocidades de acceso divergentes entre sí, con optimizaciones integradas sobre la predicción de acceso y cierto nivel de paralelismo. Incluso, cada cierto tiempo se obtienen optimizaciones en los dispositivos que podrían mejorar los rendimientos, por lo que es posible que con una generación a otra, lo que sabemos de los algoritmos y su desempeño en computadoras y cargas de trabajo reales cambie.

2.5.1 Metodología experimental

Algunos de los algoritmos que se verán en este libro son sumamente rapidos en la práctica para resolver una instancia práctica por lo que medir el desempeño de instancias solas podría no tener sentido. La acumulación de operaciones es fundamental, así como la diversidad de las instancias también lo es. Caracterizar las entradas es de vital importancia ya que la adaptabilidad a las instancias es parte de los objetivos.

Entonces, estaremos probando conjuntos de instancias, caracterizadas y estaremos utilizando tiempos promedios. También estaremos usando conteo de operaciones, por lo que los algoritmos en cuestión muchas veces serán adaptados para poder realizar este conteo.

En Julia etaremos utilizando las siguientes instrucciones:

@time expr macro que mide el tiempo en segundo utilizado por expr, también reporta el número de alojaciones de memoria. Note que reducir la cantidad de memoria alojada puede significar reducir el tiempo de una implementación, ya que el manejo de memoria dinámica es costoso.
@benchmark expr params macro del paquete BenchmarkTools que automatiza la repetición de expr para obtener diferentes mediciones y hacer un reporte, params permite manipular la forma en que se reliza la evaluación.
@btime expr params macro del paquete BenchmarkTools que mimetiza la salida de @time.

a = rand(Float32, 3, 3)
1@time a * a
2@time a * a

1: Todas las fuciones se deben compilar, la primera llamada uncluye los costos de compilación.
2: El costo sin compilación, hay una alojación que es la matriz donde se guarda el resultado.

  0.931051 seconds (2.00 M allocations: 135.473 MiB, 5.25% gc time, 99.97% compilation time)
  0.000005 seconds (1 allocation: 96 bytes)

3×3 Matrix{Float32}:
 1.06521  0.880569  0.866314
 1.43769  1.29313   1.53786
 1.11593  1.04855   1.35529

Tanto @benchmark como @btime aceptan interpolación de variables con el prefijo $ para controlar la evaluación de una expresión se debe contar como parte de lo que se quiere medir o no. Se puede combinar con el parametro setup para controlar de manera precisa las entradas para evaluar cada una de las repeticiones de expr.

using BenchmarkTools

@benchmark a * a setup=(a=rand(Float32, 3, 3))

BenchmarkTools.Trial: 10000 samples with 986 evaluations per sample.
 Range (min … max):  50.491 ns …  2.452 μs  ┊ GC (min … max): 0.00% … 96.37%
 Time  (median):     54.534 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   56.895 ns ± 35.040 ns  ┊ GC (mean ± σ):  1.75% ±  3.74%

      ▁▂▄▅▆▇██▇▆▆▄▂▂▃▃▄▄▄▃▃▂▁                    ▁▁           ▂
  ▅▅▇█████████████████████████████▇████▇██████████████████▇▅▅ █
  50.5 ns      Histogram: log(frequency) by time      70.3 ns <

 Memory estimate: 96 bytes, allocs estimate: 1.


a = rand(Float32, 3, 3)
@btime a * a setup=(a=$a)

  51.333 ns (1 allocation: 96 bytes)

3×3 Matrix{Float32}:
 0.633795  0.606148  0.137556
 0.839216  0.990184  0.17438
 0.349098  0.392372  0.454234

El parametro sample controla el número máximo de muestras que se tomarán para el análisis, y seconds limita el tiempo sobre el cual se tomarán muestras; se asegura que al menos se tomará una muestra, se debe tener en cuenta que puede costar más que seconds.¹

a = rand(Float32, 3, 3)
b = rand(Float32, 3, 3)
@benchmark a * b setup=(a=$a, b=$b) samples=1000 seconds=0.33

BenchmarkTools.Trial: 1000 samples with 974 evaluations per sample.
 Range (min … max):  69.815 ns … 669.643 ns  ┊ GC (min … max): 0.00% … 86.12%
 Time  (median):     73.586 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   75.879 ns ±  23.564 ns  ┊ GC (mean ± σ):  1.31% ±  3.78%

        ▁▂▄▅▆██▅▃▁▁     ▁                                       
  ▅▁▅▆▇█████████████▆▆█▇████▇█▇▇█▅▆▆▅▆▆▆▅▆▆▇▇▄▇▅▇▅▆▄▆▆▆▄▆▄▅▇▅▅ █
  69.8 ns       Histogram: log(frequency) by time      88.5 ns <

 Memory estimate: 96 bytes, allocs estimate: 1.

2.5.2 Ejemplo del cálculo de máximo de un arreglo y diferentes tipos de costo.

–


1function maximo(col)
    maxpos = 1
    actualizaciones = 1
    i = 2

    while i < length(col)
        if col[maxpos] < col[i]
            maxpos = i
            actualizaciones += 1
        end
        i += 1
    end

    maxpos, actualizaciones
end

1: Función que encuentra el máximo en una secuencia y devuelve su posición, y además devuelve el número de veces que se actualizó el máximo en el recorrido.

maximo (generic function with 1 method)

a = rand(UInt32, 128)
1@benchmark maximo($a) samples=100 seconds=3

1: Un análisis de desempeño usando @benchmark; probando con máximo 100 samples en 3 segundos.

BenchmarkTools.Trial: 100 samples with 600 evaluations per sample.
 Range (min … max):  198.977 ns … 231.260 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     199.373 ns               ┊ GC (median):    0.00%
 Time  (mean ± σ):   201.603 ns ±   5.308 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁█▁                                          ▁                 
  ███▁▄▁▁▁▁▁▄▁▁▄▁▇▆▄▆▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▆█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▆ ▄
  199 ns        Histogram: log(frequency) by time        217 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

Note que aunque se tiene un análisis muy detallado del desempeño, otras medidas de costo caen fuera del diseño del paquete, por lo que es necesario hacerlas por otros medios. Por ejemplo, suponga que el número de actualizaciones es nuesta medida de desempeño, un código donde se capturen las actualizaciones

1using StatsBase
2a = [maximo(rand(UInt32, 128))[2] for i in 1:100]
3quantile(a, [0.0, 0.25, 0.5, 0.75, 1.0])

1: Inclusión de un paquete para cálculo de estadísticas básicas.
2: Definición de 100 experimentos que calculan maximo sobre arreglos aleatorios.
3: Cálculo del mínimo, cuantiles 0.25, 0.5, 0.75, y el máximo, para determinar el desempeño.

5-element Vector{Float64}:
  1.0
  4.0
  6.0
  7.0
 14.0

2.6 Actividades

Comparar mediante simulación en un notebook de Jupyter o Quarto los siguientes órdenes de crecimiento:

$O(1)$ vs $O(\log n)$
$O(n)$ vs $O(n \log n)$
$O(n^2)$ vs $O(n^3)$
$O(a^n)$ vs $O(n!)$
$O(n!)$ vs $O(n^n)$
Escoja los rangos adecuados para cada comparación, ya que como será evidente después, no es práctico fijar los rangos.
Cree una figura por comparación, i.e., cinco figuras. Discuta lo observado por figura.
Cree 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.
- Use diferentes tamaños de entrada $n=100$, $n=1000$, $n=10000$ y $n=100000$.
- Note que para algunas fórmulas, los números pueden ser muy grandes, tome decisiones en estos casos y defiendalas en el reporte.
Discuta las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información, en el mismo notebook.

2.6.1 Entregable

Su trabajo se entregará en PDF y con el notebook fuente; deberá estar plenamente documentado, con una estructura que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código.

No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos:

Título del reporte, su nombre.
Introducción.
Código cercano a la presentación de resultados.
Figuras y comparación de los órdenes de crecimiento.
Análisis y simulación de costo en formato de tabla.
Conclusión. Debe abordar las comparaciones hechas y la simulación; también toque el tema de casos extremos y una $n$ variable y asintóticamente muy grande.
Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía.

2.7 Bibliografía

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

Parte I: Cap. 1, 2, 3

Se recomienda visitar el sitio https://juliaci.github.io/BenchmarkTools.jl/stable/ para más información sobre el paquete BenchmarkTools, y en particular para sus parametros, como guardar información de corridas.↩︎

--- engine: julia lang: es-MX --- # Introducción al análisis de algoritmos con Julia {#sec-analisis} Este capítulo introduce los fundamentos de análisis de algoritmos. Se introduce el concepto de modelo de cómputo, se itroduce y se motiva la notación asintótica, ya que es el lenguaje común en el análisis de algoritmos. También se mostrarán algunos de los ordenes de crecimiento más representativos, que nos permitirán comparar algoritmos que resuelvan una tarea dada, así como permitirnos catalogarlos con respecto a los recursos de computo necesarios para ejecutarlos. ## Concepto de algoritmo y estructura de datos Los algoritmos son especificaciones formales de los pasos u operaciones que deben aplicarse a un conjunto de entradas para resolver un problema, obteniendo una solución correcta a dicho problema. Establecen los fundamentos de la programación y de la manera en como se diseñan los programas de computadoras. Dependiendo del problema, pueden existir múltiples algoritmos que lo resuelvan, cada uno de ellos con sus diferentes particularidades. Así mismo, un problema suele estar conformado por una cantidad enorme de instancias de dicho problema, por ejemplo, para una lista de $n$ números, existen $n!$ formas de acomodarlos, de tal forma que puedan ser la entrada a un algoritmo cuya entrada sea una lista de números donde el orden es importante. En ocasiones, los problemas pueden tener infinitas de instancias. En este curso nos enfocaremos en problemas que pueden ser simplificados a una cantidad finita instancias. Cada paso u operación en un algoritmo esta bien definido y puede ser aplicado o ejecutado para producir un resultado. A su vez, cada operación suele tener un costo, dependiente del módelo de computación. Conocer el número de operaciones necesarias para transformar la entrada en la salida esperada, i.e., resolver el problema, es de vital importancia para seleccionar el mejor algoritmo para dicho problema, o aun más, para instancias de dicho problema que cumplen con ciertas características. Una estructura de datos es una abstracción en memoria de entidades matemáticas y lógicas que nos permite organizar, almacenar y procesar datos en una computadora. El objetivo es que la información representada puede ser manipulada de manera eficiente en un contexto específico, además de simplificar la aplicación de operaciones para la aplicación de algoritmos. ## Modelos de cómputo Un modelo de cómputo es una abstracción matemática de una computadora o marco de trabajo algorítmico que nos permite estudiar y medir los costos de los algoritmos funcionando en este modelo de tal forma que sea más simple que una computadora física real. Ejemplos de estos modelos son las máquinas de Turing, las funciones recursivas, el cálculo lambda, o la máquina de acceso aleatorio. Todas estos modelos son _equivalentes_ en sus capacidades, pero sus diferentes planteamientos permiten enfocarse en diferentes aspectos de los problemas. - [La máquina de Turing](https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing). Es un módelo creado por Alan Turing a principios del siglo XX; la idea es un dispositivo que podría ser implementada de manera mecánica si se tuvieran recursos infinitos; esta máquina puede leer y escribir en una cinta _infinita_ una cantidad de símbolos predeterminada para cada problema siguiendo una serie de reglas simples sobre lo que lee y escribe, dichas reglas y la cienta, forman una máquina de estados y memoria, que pueden realizar cualquier cálculo si el tiempo no fuera un problema. - [Funciones recursivas](https://es.wikipedia.org/wiki/Funci%C3%B3n_recursiva). Se basa en funciones que trabajan sobre los números naturales y que definen en conjunto el espacio de funciones computables. Son una herramienta abstracta que permite a los teóricos de la lógica y computación establecer los límites de lo computable. - [Cálculo lambda](https://es.wikipedia.org/wiki/C%C3%A1lculo_lambda). Es un módelo creado por Alonzo Church y Stephen Kleene a principios del siglo XX, al igual que las funciones recursivas, se fundamenta en el uso de funciones y es una herramienta abstracta con própositos similares, sin embargo el cálculo lambda no se limita a recursiones, y se enfoca en diferentes reglas de reducción y composición de funciones, y es natural la inclusión de operadores de alto nivel, aunque estos mismos sean definidos mediante un esquema funcional. - [Máquina de acceso aleatorio (RAM)](https://en.wikipedia.org/wiki/Random-access_machine). Es un módelo que describe una computadora con registros. Adiferencia de una computadora física, no tienen limitación en su capacidad, ni en la cantidad de registros ni en la precisión de los mismos. Cada registro puede ser identicado de manera única y su contenido leído y escrito mediante reglas o instrucciones formando un programa. En particular reconoce las diferencias entre registros de los programas y registros de datos, i.e., [arquitectura harvard](https://en.wikipedia.org/wiki/Harvard_architecture). Existe un número mínimo de instrucciones necesarias (i.e., incremento, decremento, poner a cero, copiar, salto condicional, parar) pero es común construir esquemas más complejos basados en estas primitivas. Se necesita un registro especial que indica el registro de programa siendo ejecutado. Los accesos a los registros tienen un tiempo constante a diferencia de otros esquemas; es el modelo más cercano a una implementación moderna de computadora. ::: {.margin-column} Una computadora moderna difiere de muchas formas de una máquina RAM. De entrada, las limitaciones físicas requieren memorias finitas y registros con valores mínimos y máximos. También se debe trabajar con una jerarquía de memoria con diferentes niveles, donde los niveles más rápidos también son los más escasos; por tanto, es importante sacar provecho de esta jerarquía siempre que sea posible. Las operaciones también tienen costos diferentes, dependiendo de su implementación a nivel de circuitería, así como también existe cierto nivel de paralelización que no esta presente en una máquina RAM, tanto a nivel de procesamiento de datos como lectura de datos y el programa, esto sin tener en cuenta la arquitecturas multitarea que ya es común en el equipo actual. ::: En este curso nos enfocaremos en especificaciones de alto nivel, donde los algoritmos pueden ser implementados en una computadora física, y estaremos contando operaciones de interés pensando en costos constantes en el acceso a memoria y en una selección de operaciones, al estilo de una máquina RAM. La selección de operaciones de interés tiene el espíritu de simplificar el análisis, focalizando nuestros esfuerzos en operaciones que acumulan mayor costo y que capturan la dinámica del resto. Adicionalmente al conteo de operaciones nos interesa el desempeño de los algoritmos en tiempo real y en la cantidad de memoria consumida, por lo que se aboradará el costo realizando mediciones experimentales, contrastando con el análisis basado en conteo de operaciones siempre que sea posible. ## Tipos de análisis La pregunta inicial sería ¿qué nos interesa saber de un algoritmo que resuelve un problema? probablemente, lo primero sería saber si produce resultados correctos. Después, entre el conjunto de las alternativas que producen resultados correctos, es determinante obtener su desempeño para conocer cuál es más conveniente para resolver un problema. En ese punto, es necesario reconocer que para un problema, existen diferentes instancias posibles, esto es el espacio de instancias del problema, y que cada una de ellas exigirían soluciones con diferentes costos para cada algoritmo. Por tanto existen diferentes tipos de análisis y algoritmos. - _Análisis de mejor caso_. Obtener el mínimo de resolver cualquier instancia posible, puede parecer poco útil desde el punto de vista de decisión para la selección de un algoritmo, pero puede ser muy útil para conocer un problema o un algoritmo. - _Análisis de peor caso_. Obtener el costo máximo necesario para resolver cualquier instancia posible del problema con un algoritmo, este es un costo que si nos puede apoyar en la decisión de selección de un algoritmo; sin embargo, en muchas ocasiones, puede ser poco informativo o innecesario ya que tal vez hay pocas instancias que realmente lo amériten. - _Análisis promedio_. Se enfoca en obtener un análisis promedio basado en la población de instancias del problema para un algoritmo dado. - _Análisis amortizado_. Se enfoca en análisis promedio pero para una secuencia de instancias. - _Análisis adaptativo_. Para un subconjunto _bien caracterizado_ del espacio de instancias de un problema busca análizar los costos del algoritmo en cuestión. La caracterización suele estar en términos de una medida de complejidad para el problema; y la idea general es medir si un algoritmo es capaz de sacar provecho de instancias _fáciles_. ## Notación asintótica Realizar un conteo de operaciones y mediciones es un asunto complejo que requiere focalizar los esfuerzos. Para este fin, es posible contabilizar solo algunas operaciones de importancia, que se supondrían serían las más costosas o que de alguna manera capturan de manera más fiel la dinámica de costos. El comportamiento asintótico es otra forma de simplificar y enfocarnos en los puntos de importancia, en este caso, cuando el tamaño de la entrada es realmente grande. Es importante mencionar, que no se esperan entradas de tamaño descomunal, ni tampoco se espera cualquier tipo de entrada. ### Notación $\Theta$ Para una función dada $g(n)$ denotamos por $\Theta(g(n))$ el siguiente conjunto de funciones: \begin{align} \Theta(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c_1, c_2 \text{ y } n_0 \text{ tal que } \right.\\ ~ & \left. 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} esto es, una función $f(n)$ pertenece al conjunto $g(n)$ si $c_1 g(n)$ y $c_2 g(n)$ pueden _cubrirla_ por abajo y por arriba, para esto deben existen las constantes positivas $c_1$ y $c_2$ y una $n$ lo suficientemente larga, e.g., para eso la constante $n_0$. La notación propiamente de conjuntos puede usarse $f(n) \in \Theta(g(n))$ pero es común en el área usar $f(n) = \Theta(g(n))$ para expresar la pertenencia; este abuso de la notación tiene ventaja a la hora de plantear los problemas de análisis. ### Notación $O$ Se utiliza para indicar una cota asintótica superior. Una función $f(n)$ se dice que esta en $O(g(n))$ si esta en el siguiente conjunto: \begin{align} O(g(n)) &= \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right.\\ ~& \left. 0 \leq f(n) \leq c g(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} La notación $O$ se usa para dar una cota superior, dentro de un factor constante. Al escribir $f(n) = O(g(n))$ se indica que $f(n)$ es miembro del conjunto $O(g(n))$; hay que notar que $f(n) = \Theta(g(n))$ implica que $f(n) = O(g(n))$, i.e., $\Theta(g(n)) \subseteq O(g(n))$. ### Notación $\Omega$ Al contrario de $O$, la notación $\Omega$ da una cota asintótica inferior. Una función $f(n)$ se dice que esta en $\Omega(g(n))$ si esta en el siguiente conjunto: \begin{align} \Omega(g(n)) = & \left\{ f(n) \mid \text{ existen las constantes positivas }c \text{ y } n_0 \text{ tal que } \right. \\ & \left. 0 \leq c g(n) \leq f(n) \text{ para todo } n \geq n_0 \right\} \\ \end{align} Dado que la $\Omega$ define una cota superior, basicamente si $f(n) = \Omega(g(n))$, entonces $f(n)$ debe estar por encima de $g(n)$ con las constantes $c$ y $n_0$ adecuadas. Al igual que la notación $O$, la notación $\Omega$ es menos estricta que $\Theta$, esto es $f(n) = \Theta(g(n))$ implica que $f(n) = \Omega(g(n))$, por lo que $\Theta(g(n)) \subseteq \Omega(g(n))$. Por tanto, si $f(n) = O(g(n))$ y $f(n) = \Omega(g(n))$ entonces $f(n) \in \Theta(g(n))$. ::: {.margin-column} Es importante conocer los ordenes de crecimiento más comunes de tal forma que podamos realizar comparaciones rápidas de costos, y dimensionar las diferencias de recursos entre diferentes tipos de costos. La notación asintótica hace uso extensivo de la diferencia entre diferentes ordenes de crecimiento para ignorar detalles y simplificar el análisis de algoritmos. ::: ### Apoyo audio-visual En los siguientes videos se profundiza sobre los modelos de cómputo y los diferentes tipos de análisis sobre algoritmos. - Parte 1: <iframe width="560" height="315" src="https://www.youtube.com/embed/uUZnpaoEQXs" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - Parte 2: <iframe width="560" height="315" src="https://www.youtube.com/embed/CkvfliomNqk" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> - Parte 3: <iframe width="560" height="315" src="https://www.youtube.com/embed/zRtjk2X2aDE" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> ### Ordenes de crecimiento <iframe width="560" height="315" src="https://www.youtube.com/embed/mX7mZH0Dz8s" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe> Dado que la idea es realizar un análisis asintótico, las constantes suelen ignorarse, ya que cuando el tamaño de la entrada es suficientemente grande, los términos con mayor orden de magnitud o crecimiento dominarán el costo. Esto es, es una simplificación necesaría. Los ordenes de crecimiento son maneras de categorizar la velocidad de crecimiento de una función, y para nuestro caso, de una función de costo. Junto con la notación asimptótica nos permite concentrarnos en razgos gruesos que se mantienen para entradas grandes, más que en los detalles, y no perder el punto de interés. A continuación veremos algunas funciones con crecimientos paradigmáticos; las observaremos de poco en poco para luego verlos en conjunto. #### Costo constante, logaritmo y lineal La siguiente figura muestra un crecimiento nulo (constante), logaritmico y lineal. Note como la función logarítmica crece lentamente. ```{julia} #| fig-width: 90% using Plots, LaTeXStrings n = 300 # 300 puntos plot(1:n, [10 for x in 1:n], label=L"c") plot!(1:n, [log2(x) for x in 1:n], label=L"\log{n}") plot!(1:n, [x for x in 1:n], label=L"n") ``` #### Costo $n \log n$ y polinomial A continuación veremos tres funciones, una función con $n\log n$ y una función cuadrática y una cúbica. Note como para valores pequeños de $n$ las diferencias no son tan apreciables para como cuando comienza a crecer $n$; así mismo, observe los valores de $n$ de las figuras previas y de la siguiente, este ajuste de rangos se hizo para que las diferencias sean apreciables. ```{julia} #| fig-width: 90% n = 7 # note que se usan menos puntos porque 300 serían demasiados para el rango plot(1:n, [x * log2(x) for x in 1:n], label=L"n\log_2{n}") 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") ``` #### Exponencial A continuación se compara el crecimiento de una función exponencial con una función polinomial. Note que la función polinomial es de grado 4 y que la función exponencial tiene como base 2; aún cuando para números menores de aproximadamente 16 la función polinomial es mayor, a partir de ese valor la función $2^n$ supera rapidamente a la polinomial. ```{julia} #| fig-width: 90% n = 20 plot(1:n, [x^4 for x in 1:n], label=L"n^4") plot!(1:n, [2^x for x in 1:n], label=L"2^n") ``` #### Crecimiento factorial Vease como la función factorial crece mucho más rápido que la función exponencial para una $n$ relativamente pequeña. Vea las magnitudes que se alcanzan en el _eje_ $y$, y comparelas con aquellas con los anteriores crecimientos. ```{julia} #| fig-width: 90% n = 20 plot(1:n, [2^x for x in 1:n], label=L"2^n") plot!(1:n, [factorial(x) for x in 1:n], label=L"n!") ``` #### Un poco más sobre funciones de muy alto costo ```{julia} #| fig-width: 90% n = 10 plot(1:n, [factorial(x) for x in 1:n], label=L"n!") plot!(1:n, [x^x for x in Int128(1):Int128(n)], label=L"n^n") ``` Vea la figura anterior, donde se compara $n!$ con $n^n$, observe como es que cualquier constante se vuelve irrelevante rapidamente; aun para $n^n$ piense en $n^{n^n}$. Note que hay problemas que son realmente costosos de resolver y que es necesario conocer si se comporta así siempre, si es bajo determinado tipo de entradas. Hay problemas en las diferentes áreas de la ciencia de datos, donde veremos este tipo de costos, y habrá que saber cuando es posible solucionarlos, o cuando se deben obtener aproximaciones que nos acerquen a las respuestas correctas con un costo manejable, es decir, mediar entre exactitud y costo. En este curso se abordaran problemas con un costo menor, pero que por la cantidad de datos, i.e., $n$, se vuelven muy costosos y veremos como aprovechar supuestos como las distribuciones naturales de los datos para mejorar los costos. ## El enfoque experimental La notación asintótica nos permite alcanzar un lenguaje común y preciso sobre los costos de problemas y algoritmos; es de especial importancia para la evaluación de las alternativas en la literatura especializada, y elegir algoritmos aún sin la necesidad de implementación. El análisis asintótico da la posibilidad de conocer el desempeño desde diferentes perspectivas como peor caso o caso promedio, utilizando un módelo de computación, y siempre pensando en entradas lo suficientemente grandes. En la práctica, existe una múltitud de razones por los cuales los problemas que se resuelven podrian no ser tan grandes como para que un algoritmo domine a otros de manera asintótica, las instancias podrían no ser tan generales como para preocuparse en el peor caso, o el caso promedio general. En muchas situaciones, es importante sacar provecho de los casos _fáciles_, sobre todo cuando el problema a resolver podría asegurar que dichos casos simples sean abundantes. Dada la complejidad detrás de definir sub-conjuntos de instancias y llevar a cabo un análisis formal, se vuelve imperativo realizar pruebas experimentales. Por otra parte, dada la complejidad de una computadora moderna, es necesario realizar evaluaciones experimentales de los algoritmos que tengan una complejidad similar. Las computadoras reales tienen una jerarquia de memoria con tamaños y velocidades de acceso divergentes entre sí, con optimizaciones integradas sobre la predicción de acceso y cierto nivel de paralelismo. Incluso, cada cierto tiempo se obtienen optimizaciones en los dispositivos que podrían mejorar los rendimientos, por lo que es posible que con una generación a otra, lo que sabemos de los algoritmos y su desempeño en computadoras y cargas de trabajo reales cambie. ### Metodología experimental Algunos de los algoritmos que se verán en este libro son sumamente rapidos en la práctica para resolver una instancia práctica por lo que medir el desempeño de instancias solas podría no tener sentido. La acumulación de operaciones es fundamental, así como la diversidad de las instancias también lo es. Caracterizar las entradas es de vital importancia ya que la adaptabilidad a las instancias es parte de los objetivos. Entonces, estaremos probando conjuntos de instancias, caracterizadas y estaremos utilizando tiempos promedios. También estaremos usando conteo de operaciones, por lo que los algoritmos en cuestión muchas veces serán adaptados para poder realizar este conteo. En Julia etaremos utilizando las siguientes instrucciones: - `@time expr` macro que mide el tiempo en segundo utilizado por `expr`, también reporta el número de alojaciones de memoria. Note que reducir la cantidad de memoria alojada puede significar reducir el tiempo de una implementación, ya que el manejo de memoria dinámica es costoso. - `@benchmark expr params` macro del paquete `BenchmarkTools` que automatiza la repetición de `expr` para obtener diferentes mediciones y hacer un reporte, `params` permite manipular la forma en que se reliza la evaluación. - `@btime expr params` macro del paquete `BenchmarkTools` que mimetiza la salida de `@time`. ```{julia} a = rand(Float32, 3, 3) @time a * a # <1> @time a * a # <2> ``` 1. Todas las fuciones se deben compilar, la primera llamada uncluye los costos de compilación. 2. El costo sin compilación, hay una alojación que es la matriz donde se guarda el resultado. Tanto `@benchmark` como `@btime` aceptan interpolación de variables con el prefijo `$` para controlar la evaluación de una expresión se debe contar como parte de lo que se quiere medir o no. Se puede combinar con el parametro `setup` para controlar de manera precisa las entradas para evaluar cada una de las repeticiones de `expr`. ```{julia} using BenchmarkTools @benchmark a * a setup=(a=rand(Float32, 3, 3)) ``` ```{julia} a = rand(Float32, 3, 3) @btime a * a setup=(a=$a) ``` El parametro `sample` controla el número máximo de muestras que se tomarán para el análisis, y `seconds` limita el tiempo sobre el cual se tomarán muestras; se asegura que al menos se tomará una muestra, se debe tener en cuenta que puede costar más que `seconds`.[^btools] [^btools]: Se recomienda visitar el sitio <https://juliaci.github.io/BenchmarkTools.jl/stable/> para más información sobre el paquete `BenchmarkTools`, y en particular para sus parametros, como guardar información de corridas. ```{julia} a = rand(Float32, 3, 3) b = rand(Float32, 3, 3) @benchmark a * b setup=(a=$a, b=$b) samples=1000 seconds=0.33 ``` ### Ejemplo del cálculo de máximo de un arreglo y diferentes tipos de costo. -- ```{julia} function maximo(col) # <1> maxpos = 1 actualizaciones = 1 i = 2 while i < length(col) if col[maxpos] < col[i] maxpos = i actualizaciones += 1 end i += 1 end maxpos, actualizaciones end ``` 1. Función que encuentra el máximo en una secuencia y devuelve su posición, y además devuelve el número de veces que se actualizó el máximo en el recorrido. ```{julia} a = rand(UInt32, 128) @benchmark maximo($a) samples=100 seconds=3 # <1> ``` 1. Un análisis de desempeño usando `@benchmark`; probando con máximo 100 samples en 3 segundos. Note que aunque se tiene un análisis muy detallado del desempeño, otras medidas de costo caen fuera del diseño del paquete, por lo que es necesario hacerlas por otros medios. Por ejemplo, suponga que el número de `actualizaciones` es nuesta medida de desempeño, un código donde se capturen las actualizaciones ```{julia} using StatsBase # <1> a = [maximo(rand(UInt32, 128))[2] for i in 1:100] # <2> quantile(a, [0.0, 0.25, 0.5, 0.75, 1.0]) # <3> ``` 1. Inclusión de un paquete para cálculo de estadísticas básicas. 2. Definición de 100 experimentos que calculan `maximo` sobre arreglos aleatorios. 3. Cálculo del mínimo, cuantiles 0.25, 0.5, 0.75, y el máximo, para determinar el desempeño. ## Actividades Comparar mediante simulación en un notebook de Jupyter o Quarto los siguientes órdenes de crecimiento: - $O(1)$ vs $O(\log n)$ - $O(n)$ vs $O(n \log n)$ - $O(n^2)$ vs $O(n^3)$ - $O(a^n)$ vs $O(n!)$ - $O(n!)$ vs $O(n^n)$ - Escoja los rangos adecuados para cada comparación, ya que como será evidente después, no es práctico fijar los rangos. - Cree una figura por comparación, i.e., cinco figuras. Discuta lo observado por figura. - Cree 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. - Use diferentes tamaños de entrada $n=100$, $n=1000$, $n=10000$ y $n=100000$. - Note que para algunas fórmulas, los números pueden ser muy grandes, tome decisiones en estos casos y defiendalas en el reporte. - Discuta las implicaciones de costos de cómputo necesarios para manipular grandes volúmenes de información, en el mismo notebook. ### Entregable Su trabajo se entregará en PDF y con el notebook fuente; deberá estar plenamente documentado, con una estructura que permita a un lector interesado entender el problema, sus experimentos y metodología, así como sus conclusiones. Tenga en cuenta que los notebooks pueden alternar celdas de texto y código. No olvide estructurar su reporte, en particular el reporte debe cubrir los siguientes puntos: - Título del reporte, su nombre. - Introducción. - Código cercano a la presentación de resultados. - Figuras y comparación de los órdenes de crecimiento. - Análisis y simulación de costo en formato de tabla. - Conclusión. Debe abordar las comparaciones hechas y la simulación; también toque el tema de casos extremos y una $n$ variable y asintóticamente muy grande. - Lista de referencias. Nota, una lista de referencias que no fueron utilizadas en el cuerpo del texto será interpretada como una lista vacía. ## Bibliografía Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (2nd ed.). MIT Press. - Parte I: Cap. 1, 2, 3